LeetCode之“链表”：Remove Duplicates from Sorted List && Remove Duplicates from Sorted List II

　 1. Remove Duplicates from Sorted List

　　题目要求：

　　Given a sorted linked list, delete all duplicates such that each element appear only once.

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

　　这道题不难。具体程序如下：

 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         if(!head || !head->next)
13             return head;
14         
15         int preVal = head->val;
16         ListNode *preNode = head;
17         ListNode *start = head->next;
18         while(start)
19         {
20             while(start && start->val == preNode->val)
21             {
22                 ListNode *next = start->next;
23                 preNode->next = next;
24                 delete start;
25                 start = next;
26             }
27             
28             if(!start)
29                 break;
30                 
31             preNode = start;
32             start = start->next;
33         }
34         
35         return head;
36     }
37 };

　 2. 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.

　　该题可以通过添加dummy节点以方便编程。具体程序如下：

 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         if(!head || !head->next)
13             return head;
14         
15         int preVal = head->val;
16         ListNode *dummy = new ListNode(0);
17         dummy->next = head;
18         ListNode *prepreNode = dummy, *preNode = head;
19         ListNode *start = head->next;
20         while(start)
21         {
22             bool flag = true;
23             while(start && start->val == preNode->val)
24             {
25                 flag = false;
26                 ListNode *next = start->next;
27                 preNode->next = next;
28                 delete start;
29                 start = next;
30             }
31             
32             if(flag)
33             {
34                 prepreNode = preNode;
35                 preNode = preNode->next;
36             }
37             else
38             {
39                 prepreNode->next = preNode->next;
40                 delete preNode;
41                 preNode = prepreNode->next;
42             }
43             
44             if(!preNode || !preNode->next)
45                 break;
46             start = preNode->next;
47         }
48         
49         head = dummy->next;
50         delete dummy;
51         dummy = nullptr;
52         
53         return head;
54     }
55 };