C语言LeetCode-Remove Duplicates from Sorted List II

考略最笨的主意:境遇值相同的就删除贰个。

对此只现出1次的数,选择尾插法插入新的队列。

 

假如p指向当前节点,q指向p的下1个节点,(上边大家用p表示p->val,即p代表p节点存储的数值)。

(1)p==q:删除p;

  (二)p!=q:把p放入新队列;

那边大家要留意第二种景况,借使p在此以前有同等的值,就算p!=q也相应删除p。为此我们设置三个flag标识,若是flag=一,表示近年来值现身多次,flag=0,表示近期值只现出3回。

那么具有情状如下:

  (1)p==q:删除p,同时令flag=1;

  (二)p!=q 且
flag=1(表示即使p不等于q,但前边至少有2个值与p相等):删除p,令flag=0;

  (三)p!=q 且 flag=0(表示p!=q,且p只出现1次):把p插入新队列。

想开那里你会发现,还有一个地点须要处理,就是新队列的头结点如何规定。

有以下3种情况(原队列):

  (a)1->壹->NULL:那种场馆新队列为空;

  (b)一->三->7->……:新队列的头结点为一;

  (c)1->一->二->四->……:新队列的头结点为贰。

换句话说,假若原队列1初阶正是重新的数量,那么在扫描的长河中,新队列的头结点是不能明确的。为此大家设置三个isHead标识,倘诺isHead=壹,表示新队列中早已有头结点,isHead=0(假设p知足(三),则把p插入新队列);表示新队列中还未有头结点(假使p知足(叁),则p就是头结点)。

循环扫描结束后(此时p不空,q=NULL),或然有如下意况:

(一)flag=1:p重复,应该删除

    1.1 )isHead=1:删除p;

    1.2)isHead=0:新队列为空。

(贰)flag=0:p只现身2回

    二.一)isHead=一:把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 }