博客挂了挺久，本来是想写点技术相关的，懒癌+技术栈.empty() == true就拖了很久，那就先水篇LeetCode刷题笔记……
Problem Description
82 Remove Duplicates from Sorted List II(Medium)
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Example 1:
1
2
|
Input: 1->2->3->3->4->4->5
Output: 1->2->5
|
Example 2:
1
2
|
Input: 1->1->1->2->3
Output: 2->3
|
Solution
题目要求我们把重复出现的节点全部删除，感觉递归的思路是比较简单的，就是在当前的递归层检测是否有跟第一个节点重复的节点，有就删除，接着继续递归。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head || !head->next )return head;
auto cur = head, next = head->next;
while(cur && next){
if(cur->val != next->val)break;
cur=next;
next = next->next;
}
if(head == cur){
head->next = deleteDuplicates(head->next);
return head;
}
cur->next = nullptr;
delete head;
return deleteDuplicates(next);
}
};
|
注意把需要删除的链(即[head, cur])的最后一个节点的next指针置为nullptr，否则因为节点的析构是递归的，可能会出现重复删除的情况，对应的报错信息大概是head-use-after-free。
众所周知，上面的递归版本按理需要额外的线性空间，而常量空间的迭代版本的可读性则会稍微差一点。
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
|
class {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head || !head->next)return head;
ListNode dummy(-1);
auto pd = &dummy;
auto start = head;
auto end = start;
while(start && end){
ListNode* prev = nullptr;
while(end && end->val == start->val){
prev = end;
end = end->next;
}
if(start == prev){
pd->next = start;
pd = start;
}else{
prev->next = nullptr;
delete start;
}
start = end;
}
pd->next = nullptr;
return dummy.next;
}
};
|
这里用了start和end代表一个重复的区间，当两者不相等证明出现了重复，需要执行delete操作。
此外，为了简化逻辑，加了个哨兵节点dummy。一个需要注意的点是循环外还要加上：
考虑下 1->2->2的情况，没有把pd->next置空的话，2会被删除两次。
最后，可以看看两者的时空复杂度：
近期评论