删除排序链表中的重复元素 II
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个已排序的链表的头节点 head。
删除原始链表中所有重复数字的节点，只留下不同的数字。
返回已排序的链表。
示例 1
示例 2
模拟答题者思考
1. 暴力：用哈希表统计每个值出现次数，再开新链表只接出现一次的节点——正确但 O(n) 额外空间，且没利用「已排序、相同值相邻」。
2. 和 #83（每个值只删多余份、保留一份）对比：本题是「只要出现过重复，该值的所有节点都删」。因此不能边扫边保留，而要识别「连续相同值的一段」并整段跳过。
3. 有序性：重复值必然形成连续块。若 curr.next 与 curr 同值，则 curr 所在块至少两个节点，整块作废；用 while 把 curr 推到块后第一个不同值（或 null）。
4. 谁改 next？删除的是「下一段要接上的位置」的前驱。用 prev 表示结果链尾；跳过重复块后 prev.next = curr，且 prev 不前进（因为刚删掉的块可能包含原 prev 的下一个节点）。仅当 curr 无重复后继时才 prev = curr。
5. 头节点可能是重复块（如 [1,1,1,2,3]）——加 dummy，令 prev = dummy，与删中间块同一套逻辑；一遍扫描 O(n)，O(1) 额外指针。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dummy | ListNode* | 定义：哨兵头节点，dummy.next = head维护：始终位于真实头节点之前，便于在「整段重复块含头节点」时改链 更新：创建后不再移动，最终返回 dummy.next |
prev | ListNode* | 定义：结果链表中「已确定保留」的最后一个节点，初始为 dummy维护： dummy.next..prev 均为只出现一次的节点；遇到重复块时 prev 不动，只改 prev.next 跳过整段更新：当前节点 curr 无重复后继时 prev = curr；跳过重复块后执行 prev.next = curr（curr 已是下一段首节点） |
curr | ListNode* | 定义：扫描指针，从 head 向右检查是否进入重复块维护：若 curr.val == curr.next.val，则从 curr 起整段同值节点都要删除更新：无重复时 curr = curr.next；有重复时 while curr and curr.val == dup_val: curr = curr.next，再令 prev.next = curr |
落码步骤
1. dummy = ListNode(0, head)，prev = dummy，curr = head
2. 当 curr 非空：若 curr.next 存在且 curr.val == curr.next.val，记下 dup_val，while curr and curr.val == dup_val: curr = curr.next，再 prev.next = curr
3. 否则（curr 在结果中保留）：prev = curr，curr = curr.next
4. 返回 dummy.next
代码实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head) # 哨兵，处理头节点即重复块
prev, curr = dummy, head
while curr:
if curr.next and curr.val == curr.next.val:
dup_val = curr.val
while curr and curr.val == dup_val: # 跳过整段重复块
curr = curr.next
prev.next = curr
else:
prev = curr
curr = curr.next
return dummy.nextclass Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode dummy(0, head); // 哨兵，处理头节点即重复块
ListNode* prev = &dummy;
ListNode* curr = head;
while (curr) {
if (curr->next && curr->val == curr->next->val) {
int dupVal = curr->val;
while (curr && curr->val == dupVal) // 跳过整段重复块
curr = curr->next;
prev->next = curr;
} else {
prev = curr;
curr = curr->next;
}
}
return dummy.next;
}
};
// 时间 O(n)，空间 O(1)复杂度分析
O(n)
O(1)
常见坑
套用 #83 的「保留一份」逻辑：本题重复值要全部删除，不能把 curr 当作保留节点直接 prev = curr 再只删后继。
跳过重复块后误执行 prev = curr：此时 curr 尚未验证是否无重复，应等下一轮循环；只有走 else 分支才移动 prev。
忘记 dummy：头节点属于重复块时（如全 1），没有前驱可改 next，必须用哨兵统一接链。
必测边界 Case
head = [] → []（循环不执行，返回 dummy.next == null）
head = [1,2,3] → [1,2,3]（始终走 else，prev 逐节点前进）
head = [1,1,1] → []（prev 停在 dummy，prev.next = null）
head = [1] → [1]（无 curr.next，直接保留）