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

题目描述

这是 LeetCode 上的 82. 删除排序链表中的重复元素 II ,难度为 中等

存在一个按升序排列的链表,给你这个链表的头节点 head,请你删除链表中所有存在数字重复情况的节点,只保留原始链表中没有重复出现的数字。

返回同样按升序排列的结果链表。

示例 1:

1
2
3
输入:head = [1,2,3,3,4,4,5]

输出:[1,2,5]

示例 2:

1
2
3
输入:head = [1,1,1,2,3]

输出:[2,3]

提示:

  • 链表中节点数目在范围 $[0, 300]$ 内
  • $-100 <= Node.val <= 100$
  • 题目数据保证链表已经按升序排列

基本思路

几乎所有的链表题目,都具有相似的解题思路。

  1. 建一个虚拟头节点 dummy 以减少边界判断,往后的答案链表会接在 dummy 后面
  2. 使用 tail 代表当前有效链表的结尾
  3. 通过原输入的 head 指针进行链表扫描

我们会确保「进入外层循环时 head 不会与上一节点相同」,因此插入时机:

  1. head 已经没有下一个节点,head 可以被插入
  2. head 有一下个节点,但是值与 head 不相同,head 可以被插入

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode();
ListNode tail = dummy;
while (head != null) {
// 进入循环时,确保了 head 不会与上一节点相同
if (head.next == null || head.val != head.next.val) {
tail.next = head;
tail = head;
}
// 如果 head 与下一节点相同,跳过相同节点
while (head.next != null && head.val == head.next.val) head = head.next;
head = head.next;
}
tail.next = null;
return dummy.next;
}
}

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* dummy = new ListNode();
ListNode* tail = dummy;
while (head != nullptr) {
// 进入循环时,确保了 head 不会与上一节点相同
if (head->next == nullptr || head->val != head->next->val) {
tail->next = head;
tail = head;
}
// 如果 head 与下一节点相同,跳过相同节点
while (head->next != nullptr && head->val == head->next->val) head = head->next;
head = head->next;
}
tail->next = nullptr;
return dummy->next;
}
};

Python 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
tail = dummy
while head:
# 进入循环时,确保了 head 不会与上一节点相同
if not head.next or head.val != head.next.val:
tail.next = head
tail = head
# 如果 head 与下一节点相同,跳过相同节点
while head.next and head.val == head.next.val: head = head.next
head = head.next
tail.next = None
return dummy.next

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function deleteDuplicates(head: ListNode | null): ListNode | null {
const dummy: ListNode = new ListNode();
let tail: ListNode | null = dummy;
while (head) {
// 进入循环时,确保了 head 不会与上一节点相同
if (!head.next || head.val !== head.next.val) {
tail.next = head;
tail = head;
}
// 如果 head 与下一节点相同,跳过相同节点
while (head.next && head.val === head.next.val) head = head.next;
head = head.next;
}
tail.next = null;
return dummy.next;
};

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$

拓展

如果问题变为「相同节点保留一个」,该如何实现?

还是类似的解题思路。

  1. 建一个虚拟头节点 dummy 以减少边界判断,往后的答案链表会接在 dummy 后面
  2. 使用 tail 代表当前有效链表的结尾
  3. 通过原输入的 head 指针进行链表扫描

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return head;
ListNode dummy = new ListNode(-109);
ListNode tail = dummy;
while (head != null) {
// 值不相等才追加,确保了相同的节点只有第一个会被添加到答案
if (tail.val != head.val) {
tail.next = head;
tail = tail.next;
}
head = head.next;
}
tail.next = null;
return dummy.next;
}
}

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return head;
ListNode* dummy = new ListNode(-109);
ListNode* tail = dummy;
while (head) {
// 值不相等才追加,确保了相同的节点只有第一个会被添加到答案
if (tail->val != head->val) {
tail->next = head;
tail = tail->next;
}
head = head->next;
}
tail->next = nullptr;
return dummy->next;
}
};

Python 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head: return head
dummy = ListNode(-109)
tail = dummy
while head:
# 值不相等才追加,确保了相同的节点只有第一个会被添加到答案
if tail.val != head.val:
tail.next = head
tail = tail.next
head = head.next
tail.next = None
return dummy.next

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function deleteDuplicates(head: ListNode | null): ListNode | null {
if (!head) return head;
const dummy: ListNode = new ListNode(-109);
let tail: ListNode | null = dummy;
while (head) {
// 值不相等才追加,确保了相同的节点只有第一个会被添加到答案
if (tail.val !== head.val) {
tail.next = head;
tail = tail.next;
}
head = head.next;
}
tail.next = null;
return dummy.next;
};

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.82 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!