[LeetCode] Remove Duplicates from Sorted List II

For example,

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

Given 1->1->1->2->3, return 2->3.

问题描述：给定一个已经排序的单链表，删除所有有相同数字的节点，只留下原始链表中的不同数字。

要删除相同数字的节点，可以用两个指针遍历这个链表，当两个数字相同时，就将后面的节点删除。那么，如果当前遍历的两个节点不相同时，是否可以继续往后遍历呢？答案是不行，如果当前两个节点的数字不同，有可能前一个指针指向的是刚刚有相同数字的节点，此时，应该删除。而且，如果要删除当前遍历的节点，就要保存该节点的前面节点的指针，因此，程序中有四个变量：

（1）ListNode *p 遍历链表的第一个指针

（2）ListNode *q 遍历链表的第二个指针

（3）ListNode *r 当p是头节点时，r指向头节点，当p不是头节点时，r指向p的后继，r用于删除p本身

（4）bool set 布尔变量，用于保存是否找到了相同节点，因为即使p的值域和q的值域不同，也不能肯定p是否是已经找到的相同节点，于是用set来进行指示

class Solution {  
public:  
    ListNode *deleteDuplicates(ListNode *head) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        if(head == NULL)  
            return head;  
  
        ListNode *p, *q, *r;  
        bool set = false;  
  
        p = head;  
        q = head->





next;  
        r = head;  
        while(q) {  
            if(p->val == q->val) {  
                set = true;  
                p->next = q->next;  
                delete q;  
                q = q->next;  
            }  
            else if(p->val != q->val && !set) {  
                r = p;  
                p = q;  
                q = q->next;  
            }  
            else if(p->val != q->val && set) {  
                if(p == head) {  
                    head = p->next;  
                    delete p;  
                    p = q;  
                    q = q->next;  
                }  
                else {  
                    r->next = p->next;  
                    p = r->next;  
                    q = q->next;  
                }  
                set = false;  
            }  
        }  
          
        if(set) {  
            if(p == head) {  
                head = p->next;  
                delete p;  
            }  
            else {  
                r->next = p->next;  
                delete p;  
            }  
        }  
  
        return head;  
    }  
};