LeetCode-Remove Duplicates from Sorted List II

考略最笨的方法：遇到值相同的就删除一个。

对于只出现一次的数，采用尾插法插入新的队列。

假设p指向当前节点，q指向p的下一个节点，（下面我们用p表示p->val，即p代表p节点存储的数值）。

（1）p==q：删除p；

　　（2）p！=q：把p放入新队列；

这里我们要注意第二种情况，如果p之前有相同的值，即使p！=q也应该删除p。为此我们设置一个flag标识，如果flag=1，表示当前值出现多次，flag=0，表示当前值只出现一次。

那么所有情况如下：

　　（1）p==q：删除p，同时令flag=1；

　　（2）p！=q 且 flag=1（表示虽然p不等于q，但前面至少有一个值与p相等）：删除p，令flag=0；

　　（3）p！=q 且 flag=0（表示p！=q，且p只出现一次）：把p插入新队列。

想到这里你会发现，还有一个地方需要处理，就是新队列的头结点如何确定。

有以下3种情况（原队列）：

　　（a）1->1->NULL：这种情况新队列为空；

　　（b）1->3->7->……：新队列的头结点为1；

　　（c）1->1->2->4->……：新队列的头结点为2。

换句话说，如果原队列一开始就是重复的数据，那么在扫描的过程中，新队列的头结点是无法确定的。为此我们设置一个isHead标识，如果isHead=1，表示新队列中已经有头结点，isHead=0（如果p满足（3），则把p插入新队列）；表示新队列中还没有头结点（如果p满足（3），则p就是头结点）。

循环扫描结束后（此时p不空，q=NULL），可能有如下情况：

（1）flag=1：p重复，应该删除

　　　　1.1 ）isHead=1：删除p；

　　　　1.2）isHead=0：新队列为空。

（2）flag=0：p只出现一次

　　　　2.1）isHead=1：把p插入新队列；

　　　　2.2）isHead=0：p是新队列的头结点。

下面贴出C语言的实现：（但是该实现耗时较多，原因应该是循环中条件分支过多）

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     struct ListNode *next;
 6  * };
 7  */
 8 struct ListNode* deleteDuplicates(struct ListNode* head) {
 9     if (!head) return NULL;
10     if (!head->next) return head;
11     
12     struct ListNode *p = NULL;
13     struct ListNode *q = NULL;
14     struct ListNode *r = NULL;
15     struct ListNode *newHead = NULL;//newHead denotes the new list
16     int flag = 0, isHead = 0;//isHead=0 denotes there is no head in newHead
17     p = head, q = p->next;//p denotes the current node,q denotes the next node 
18     
19     flag = 0;//there are no duplications
20     while (q)
21     {
22         if (p->val != q->val && flag == 0)//put p in new list 
23         {
24             if (!isHead)
25             {
26                 newHead = r = p;
27                 isHead = 1;//there is already head in newHead
28                 r->next = NULL;                    
29             }
30             else
31             {
32                 r->next = p;
33                 r = p;        
34                 r->next = NULL;
35             }
36         }
37         else if (p->val != q->val && flag == 1)//delete p
38             flag = 0;
39         else if (p->val == q->val)//delete p
40             flag = 1;
41             
42         p = q;
43         q = q->next;
44     }
45     
46     if (flag == 1)
47     {
48         if (!isHead)
49             newHead == NULL;
50         else
51             r->next = NULL;
52     }
53     else
54     {
55         if (!isHead)
56         {
57             newHead = p;
58             newHead->next = NULL;
59         }
60         else
61         {
62             r->next = p;
63             r = p;
64             r->next = NULL;
65         }
66     }
67     
68     return newHead;
69 }