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;
    }
}