[LeetCode] 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.

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

关键是记录三个指针，当前指针p, p的父亲pPre, pPre的父亲pPrePre。

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *deleteDuplicates(ListNode *head) {
12         // Start typing your C/C++ solution below
13         // DO NOT write int main() function
14         if (head == NULL)
15             return NULL;
16         
17         ListNode *pPrePre = NULL;    
18         ListNode *pPre = NULL;
19         ListNode *p = head;
20         int key = INT_MAX;
21         
22         while(p)
23         {
24             if (key != p->val)
25             {
26                 key = p->val;
27                 pPrePre = pPre;
28                 pPre = p;
29                 p = p->next;
30             }
31             else
32             {
33                 if (pPre && pPre->val == key)
34                 {
35                     ListNode *pNext = p->next;
36                     if (pPrePre)
37                         pPrePre->next = pNext;
38                     if (head == pPre)
39                         head = pNext;                   
40                     delete pPre;
41                     delete p;
42                     pPre = pPrePre;
43                     p = pNext;                       
44                 }
45                 else
46                 {
47                     ListNode *pNext = p->next;
48                     if (pPre)
49                         pPre->next = pNext;
50                     if (head == p)
51                         head = pNext;
52                     delete p;
53                     p = pNext;
54                 }
55             }
56         }
57         
58         return head;
59     }
60 };