82.Remove Duplicates from Sorted List II

Tags: Medium Linked List

Links: https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

---

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

---

/**
 * 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 == NULL || head -> next == NULL) return head;

        ListNode *dummy = new ListNode(0);
        dummy -> next = head;
        ListNode *head2 = dummy, *pre = head2 -> next, *cur = pre -> next;
        bool flag = false; //是否出现了重复元素

        do{
            if (pre -> val == cur -> val){
                cur = cur -> next;
                pre -> next = cur;
                head2 -> next = pre;
                flag = true;
                continue;
            }

            cur = cur -> next;
            pre = pre -> next;

            if (flag){
                head2 -> next = pre;
                flag = false;
            } 
            else head2 = head2 -> next;
        } while(pre -> next);

        if (flag){
            pre = pre -> next;
            head2 -> next = pre;
        }

        return dummy -> next;
    }
};

思考方式：

先考虑两种情况，一种无重复元素，另一种存在重复元素。

无重复元素：代码就是28 + 29 + 35，很容易想到。

存在重复元素：重复元素出现在首、中、尾三个位置，重复元素两个连续（2 2 3 3的情况）。

特殊情形：空链表，只有一个元素，两个相同的元素，连续两组相同元素（[2 2 3 3]的情况）

有重复元素我们就增加一个flag来记录下一次处理时，之前是否是重复元素。用一个head2来记录pre之前的节点。

38 - 41 是处理[1 1]的情况。