[每日 LeetCode] 82. Remove Duplicates from Sorted List II

Description:

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

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

思路：本题是[每日 LeetCode] 83. Remove Duplicates from Sorted List 的升级版，比较麻烦的地方是要求删除所有重复的节点。考虑由于链表开头可能会有重复节点，被删掉的话头指针会改变，而最终却还需要返回链表的头指针。所以需要另外定义一个新节点，链上原链表，然后定义两个额外指针，即 pre 指针和一个 curr 指针，每当 pre 指针指向新建的节点，curr 指针从下一个位置开始往下遍历，遇到相同的则继续往下，直到遇到不同项时，把 pre 指针的 next 指向下面那个不同的元素。如果 curr 指针遍历的第一个元素就不相同，则直接把 pre 指针向下移一位。

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) 
            return head;
        ListNode *dummy = new ListNode(-1), *pre = dummy;
        dummy->next = head;
        while (pre->next) {
            ListNode *curr = pre->next;
            while (curr->next && curr->next->val == curr->val) {
                curr = curr->next;
            }
            if (curr != pre->next) 
                pre->next = curr->next;
            else 
                pre = pre->next;
        }
        return dummy->next;
    }
};

运行时间：8ms

运行内存：9.3M