LeetCode 82 Remove Duplicates from Sorted List II(从已排序链表中移除重复元素)(Linked List)(*)

翻译

给定一个已排序链表,删除所有的重复节点,只保留原始链表中独特的数字。

例如,
给定 1->2->3->3->4->4->5, 返回 1->2->5.
给定 1->1->1->2->3, 返回 2->3.

原文

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

分析

这类问题一般都要特地构造一个头部,比如说

1 -> 1 -> 2 -> 3 -> NULL

这个时候如果把1删掉了,那么head放在哪?相反,如果是

x -> 1 -> 1 -> 3 -> NULL

这样的话,把1都删掉了,x还可以充当头部,不管取什么值都可以,反正最后返回的肯定是

return x->next;

这里写图片描述

不知道我排版得有没有对齐,应该不影响阅读吧。反正核心思想是,如果p所在的位置和下一个位置的值相同,就一直往后走。而且走到最后一个3的时候,记得还要再走一步才能到4。

那么c和p之间如何跨越这么大的鸿沟呢,最后一句c->next = p,就将它们有紧密的联合起来了,绝对是一对好CP,这也是我给它们这样命名的原因。

之所以要设定这么一个CP,就是因为在这里不像上一题一样,删除重复节点的时候是都要删掉,不会留下一个。换句话说,如果是每次只删一个,最后肯定会有一个留下没有被删除,因为它前后重复都删掉了,剩下继续比较的都是不重复的。因此应该加一个标记,用于最后一次性删除。这里的删除也就是跳过一个节点。

LeetCode 83 Remove Duplicates from Sorted List(从已排序链表中移除重复元素)(Linked List)

代码

C Plus Plus

ListNode *deleteDuplicates(ListNode *head) {
  if (head == NULL || head->next == NULL) return head;
  ListNode *newHead = new ListNode(0);
  newHead->next = head;

  ListNode *c = newHead, *p = head;
  while (p != NULL && p->next != NULL) {
    if (p->val != p->next->val) {
      c = c->next;
      p = p->next;
    } else {
      while (p->next != NULL && p->val == p->next->val) {
        p = p->next;
      }
      p = p->next;
      c->next = p;
    }
  }
  return newHead->next;
}

做一个小幅修改,看上去更加科学一点。

updated at 2016/08/14
ListNode* deleteDuplicates(ListNode *head) {
  if (!head || !head->next) return head;
  ListNode *newHead = new ListNode(0);
  newHead->next = head;
  ListNode *c = newHead, *p = c->next;

  while (c->next && c->next->next) {
    if (c->next->val == c->next->next->val) {
      p = p->next;
      while (p->next && p->val == p->next->val) {
        p = p->next;
      }
      c->next = p->next;
    } else {
      c = c->next;
      p = p->next;
    }
  }
  return newHead->next;
}

Java

updated at 2016/09/23
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
public class Solution {
     public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode c = newHead, p = c.next;

        while (c.next != null && c.next.next != null) {
            if (c.next.val == c.next.next.val) {
                p = p.next;   // 标记要跳过的节点
                while (p.next != null && p.val == p.next.val) {
                    p = p.next;  // 继续循环标记要删除的节点
                }
                c.next = p.next;
            } else {
                c = c.next;
                p = p.next;
            }
        }
        return newHead.next;
    }
}

推荐文章

如何在Windows环境下将svn库转换为git

如何在Windows环境下将svn库转换为git

推荐文章

用Aeson解析嵌套的对象数组

用Aeson解析嵌套的对象数组

推荐文章

尝试从ruby1.8.7升级到1.9.2,同时仍然使用rails2.3.8

尝试从ruby1.8.7升级到1.9.2,同时仍然使用rails2.3.8

推荐文章

如何使用Hudson/SVN/Sonar/MSBuild配置CI服务器

如何使用Hudson/SVN/Sonar/MSBuild配置CI服务器

推荐文章

如何从model+ModelForm获取textarea?

如何从model+ModelForm获取textarea?

推荐文章

each()循环截断最后一个值

each()循环截断最后一个值

推荐文章

如何在字典的第一个索引中插入元素?

如何在字典的第一个索引中插入元素?

推荐文章

有没有可能在框架中查看.m文件中的源代码?

有没有可能在框架中查看.m文件中的源代码?

推荐文章

“只能在同质AppDomain中执行动态操作”错误

“只能在同质AppDomain中执行动态操作”错误

推荐文章

利用VBA中的放大API实现屏幕放大

利用VBA中的放大API实现屏幕放大

推荐文章

带CGPoint迭代器的atan2

带CGPoint迭代器的atan2

推荐文章

SAX XML解析器引发空指针异常

SAX XML解析器引发空指针异常

推荐文章

java双精度

java双精度

推荐文章

如何显示从零开始的图表(线系列)?

如何显示从零开始的图表(线系列)?

推荐文章

playframework:如何传递参数以包含

playframework:如何传递参数以包含

推荐文章

C#TCP插座。接收重用套接字时出现问题

C#TCP插座。接收重用套接字时出现问题