Google+ Followers

Monday, March 18, 2013

[LeetCode] Remove Duplicates from Sorted List II, Solution


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.
» Solve this problem

[Thoughts]
实现题。前面加一个Safeguard,这样可以避免处理头结点的复杂。

[Code]
1:       ListNode *deleteDuplicates(ListNode *head) {  
2:            if(head == NULL) return head;  
3:            ListNode *G = new ListNode(INT_MIN);  
4:            G->next = head;  
5:            ListNode *cur = G, *pre = head;  
6:            while(pre!=NULL)  
7:            {  
8:                 bool isDup = false;  
9:                 while(pre->next!=NULL && pre->val == pre->next->val)  
10:                 {  
11:                      isDup = true;  
12:                      ListNode *temp = pre;  
13:                      pre = pre->next;  
14:                      delete temp;  
15:                 }  
16:                 if(isDup)  
17:                 {  
18:                      ListNode *temp = pre;  
19:                      pre = pre->next;  
20:                      delete temp;  
21:                      continue;  
22:                 }  
23:                 cur->next = pre;  
24:                 cur = cur->next;  
25:                 pre= pre->next;  
26:            }  
27:            cur->next = pre;  
28:            ListNode *temp = G->next;  
29:            delete G;  
30:            return temp;      
31:       }  


Post a Comment