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.

http://www.lintcode.com/en/problem/remove-duplicates-from-sorted-list-ii/

Discussion

画个图，一切都明白了。

Solution

class Solution{
public:
    /**
     * @param head: The first node of linked list.
     * @return: head node
     */
    ListNode * deleteDuplicates(ListNode *head) {
        // write your code here
        if(head == NULL) return NULL;
        ListNode dummy(head->val + 1);
        dummy.next = head;
        ListNode *cur = head;
        ListNode *pre = &dummy;
        while(cur != NULL) {
            bool iDup = false;
            while(cur->next != NULL && cur->val == cur->next->val) {
                ListNode *tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
                iDup = true;
            }
            if(iDup) {
                pre->next = cur->next;
                ListNode *tmp = cur;
                cur = cur->next;
                delete tmp;
            } else {
                pre = cur;
                cur = cur->next;
            }
        }
        return dummy.next;
    }
};