82-83删除链表的重复元素

82. 删除排序链表中的重复元素 II

下面是题目

下面是题目给出的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {

}
};

这里给出两种放法,第一种是我通过模仿1171的思路通过unordered_map存储来实现的,第二种是更快的解题方法

第一种

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
这道题,我才用遍历两边的思路完成所有重复节点的删除
拿123344556来做实验
第一道遍历,将重复的节点删除,但保留重复的第一个节点,同时把3,4,5存储到set中
比如现在,链表已经变成123456了
第二道遍历,判断节点值是否在set中出现过,如果出现,则删除,比如3,4,5已经在表中了。现在删除他们 最后的得到126
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode*dummy = new ListNode(0);
dummy->next=head;
//思路差不多,我也是利用unordered_map 来记录一个是否重复的元素
set<int>judge;
if(!head) return NULL;
ListNode *p = head;
while( p->next)
{
if(p->next->val==p->val)
{
p->next = p->next->next;
judge.insert(p->val);
}else
p = p->next;
}
p = dummy;
//第二段遍历,删除存储在set中的节点
while(p->next)
{
if(judge.find(p->next->val)!=judge.end())
p->next = p->next->next;
else
p = p->next;
}
return dummy->next;
}
};

第二种解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
这个方法也是遍历,但是没有依赖其他容器,而且只遍历了一遍
思路:
通过两个指针来实现遍历操作
下面的题解以12333445为例

*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* p = new ListNode(0);
p->next = head;
head = p;
while(p->next){
if(!p->next->next) break;
//这里把p当作第一个重复节点的前一个结点进行运算,现在p为2,但是接下来是三个相同节点345
if(p->next->val == p->next->next->val){
//进入if语句后,把i指向第5个节点。如果第五个节点或者后面的节点还是和第3个节点的值一样,那就移动i,直到不一样位置,再把当前的p节点指向i,完成中间所有重复节点的删除
ListNode* i = p->next->next->next;
while(i){
if(i->val == p->next->val){
i = i->next;
}else{
break;
}
}
//更新p后面节点的值,也就是现在p->next = 4,开始下一轮遍历!
p->next = i;
}else{
//更新p的值,寻找下个重复的节点
p = p->next;
}
}
head = head->next;
return head;
}
};

83 删除排序链表中的重复元素

下面是题目给出的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {

}
};

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* deleteDuplicates(ListNode* head) {
ListNode*cur = head;
ListNode*toDelete = NULL;
if(!head) return NULL;
while(cur->next)
{
if(cur->next->val==cur->val)
{
toDelete = cur ->next;
cur->next= cur->next->next;
delete toDelete;
toDelete = NULL;
}
else
{
cur=cur->next;
}
}
return head;
}
-------------本文结束,感谢您的阅读-------------