面试题57 删除链表中重复的结点

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6         val(x), next(NULL) {
 7     }
 8 };
 9 */
10 class Solution {
11 public:
12     ListNode* deleteDuplication(ListNode* pHead)
13     {
14         if (!pHead)
15             return NULL;
16         if (!pHead->next)
17             return pHead;
18         
19         ListNode* p = new ListNode(-1);
20         ListNode* q = pHead;
21         p->next = q;
22         ListNode* r = q->next;
23         
24         ListNode* h = p;
25         int flag;
26         while (r){
27             flag = 0;
28             while (r != NULL && q->val == r->val){
29                 q->next = r->next;
30                 delete r;
31                 r = q->next;
32                 flag = 1;
33             }
34             if (flag == 1){
35                 if (r == NULL){
36                     p->next = NULL;
37                     delete q;
38                 }
39                 else{
40                     p->next = r;
41                     delete q;
42                     q = r;
43                     r = r->next;
44                 }
45             }
46             else{
47                 p = p->next;
48                 q = q->next;
49                 r = r->next;
50             }
51         }
52         return h->next;
53     }
54 };