【LC 82】删除排序链表中的重复元素 II：为什么头节点这里必须有个 dummy
适用读者：做过 LC 83（保留一个），觉得"删重复"已经会了，然后被这题的一个都别留卡住的人
技术栈：Python 为主，附 Java 版
难度：中等（代码 15 行，但 prev 到底什么时候前进，是最容易写错的地方）
收获：dummy 哨兵「到底在解决什么问题」的准确答案，以及 prev / curr 这对指针的推进规则
题目
给你一个已排序的链表的头
head，
删除原始链表中所有重复数字的节点，只留下不同的数字。
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
解释：3 和 4 都出现过重复，所以它们一个都不留
输入：head = [1,1,1,2,3]
输出：[2,3]
解释：1 出现了三次，全删；2、3 各只出现一次，保留
注意加粗那句：
出现过重复的值，一个都不留。这跟 LC 83 是两回事 —— 83 是"每个值留一个"，结果会是
[1,2,3,3,4,4,5] → [1,2,3,4,5]。82 要的是
[1,2,5]。
出处备注：暑期实习面经里高频出现。这题被选中的原因往往是它和 LC 83 只差一行条件，用来快速分辨"真理解指针"还是"记得模板"。
链表节点的定义，沿用前几篇：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
一、先想清楚：为什么这题比 LC 83 难
1.1 排序这个条件给了什么
链表已经排好序，所以
重复的元素一定挨在一起。不需要哈希表去统计每个值出现几次，只要顺着走，看到"当前节点和下一个节点值相同"就知道碰上重复了。
这是这题唯一一个"送分"的地方：
判重不用回看，只看邻位，
O(1) 空间是白送的。
1.2 真正的难点：删除需要前驱
删除一个节点
x，在单链表里只有一种做法：
也就是说，
要删一个节点，你必须先拿到它的前驱。
现在问题来了：LC 83 里，重复时保留第一个、删后面几个 —— 被删的节点总是有前驱的（前驱就是保留下来的那个）。所以 LC 83 里
prev 永远安全。
但 82 要"一个都不留"：重复段里的
第一个节点也要删。而那一段的第一个节点，它的前驱可能是……
原来的 head 自己。
最极端的例子：
这里
head 本身（第一个
1）就要被删掉。可
head 没有前驱 —— 你没法执行
head 的前驱.next = head.next，因为
head 的前驱 根本不存在。
1.3 dummy 哨兵：给头节点一个人造的"前驱"
解法是
在头节点前面架一个假的节点：
现在
dummy 就是头节点的前驱了，删第一个
1 变成一次普通的删除操作：
dummy.next = 1.next。
没有一个节点是特殊的。
dummy = ListNode(0)
dummy.next = head
...
return dummy.next # 返回 dummy.next，而不是 head
两个必须记住的细节：
- 返回
dummy.next 而不是 head。因为 head 自己可能已经被摘掉了，那时 head 指向的是一个已经脱离链表的孤儿节点。dummy.next 才永远是正确的答案。
dummy 的值随便填。它不参与比较，0 只是习惯（有些题解用 -1；如果值域可能到 -1，用一个足够小的负数更稳）。
顺便说一句：LC 19（删除倒数第 N 个）也用了 dummy，但那题的理由是"可能要删头节点"。同一个技巧，同一个动机 —— 只要你意识到"操作可能落到头节点上"，就该条件反射地架一个 dummy。
二、双指针的推进规则（这一步最容易写错）
架好 dummy 之后，需要两个指针：
prev：已经确认安全的节点的尾巴，也就是"最后一个确定要保留的节点"；curr：正在检查的位置。
主循环的骨架长这样：
prev, curr = dummy, head
while curr:
if curr.next and curr.val == curr.next.val:
# 发现重复 —— 这里要整段跳掉
...
else:
prev = curr
curr = curr.next
else 那一支：只有确认 curr 不属于任何重复段时，prev 才跟着前进。
为什么？因为一旦发现重复，
curr 会被推着往前跑（去跳过整段），而
prev 必须
钉在原地 —— 它是那一段的"接回点"。等
curr 跑出重复段了，用
prev.next = curr 一次把中间那整段摘掉。
如果
prev 跟着一起推，中间那几个被摘掉的节点就会出现在
prev 和
curr 之间，
prev.next = curr 之后链表里还挂着半截垃圾。
2.1 发现重复之后做什么
if curr.next and curr.val == curr.next.val:
dup_val = curr.val
while curr and curr.val == dup_val:
curr = curr.next # curr 一路冲到重复段之外
prev.next = curr # 一次接上，中间整段被摘出
注意这里
没有 prev = prev.next。
prev 就是不动。
内层
while curr and curr.val == dup_val 里那个
curr and 不能省：如果重复段一直延伸到链表末尾（比如
1 → 2 → 2），
curr 会一路跑到
None，没有
curr and 就会在
curr.val 上抛
AttributeError。
2.2 为什么内层用「值」比较就够了
curr.val == dup_val 比的是
值，不是节点 —— 这和 LC 160 相交链表里"必须比引用"正好相反，值得对照记一下：
判据永远跟着
题目在问什么走，别背成一条死规则。
2.3 完整代码
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head) # 给头节点造一个前驱
prev, curr = dummy, head
while curr:
# 发现重复：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 # 一次摘掉整段；prev 不动
else:
prev = curr # 确认安全，prev 才前进
curr = curr.next
return dummy.next # 不是 head —— head 可能已被摘
三、动画：看着 prev 停在原地等
下面这个动画把
1 → 2 → 3 → 3 → 4 → 4 → 5 的全程拆成 15 帧。留意三件事：
- 最左边那个虚线框是 dummy：它在内存里并不存在，是解法凭空造出来的前驱。整条链的实际起点是它右边的
1；
- 橙色的框是"当前这段重复"：被框住的节点一会儿要被整段摘掉。框里节点上面那条橙线（
curr）会往右跑，而下面那条绿线（prev）一动不动 —— 这个错位就是本题的全部难点；
- 摘链那一帧：
prev 伸出一条橙色虚线弧，跨过整段重复节点落到 curr 上，那条弧就是 prev.next = curr 这个赋值。被摘的节点同时变灰、被打上删除线。
看完动画再回头看 2.1 节那句"
prev 就是不动"，画面上就是绿线钉在原地、橙线越跑越远。
四、完整推演表
用动画里的例子：
pool 下标: 0=1 1=2 2=3 3=3 4=4 5=4 6=5
1 → 2 → 3 → 3 → 4 → 4 → 5
数一下每一帧的 prev 是否合理：第 3–6 帧
prev 一直是
2（
四个帧没动过），第 8–11 帧一直是
3。
"发现重复 → prev 冻结"在这张表里一眼可见。
表里 skip 帧的 curr 有时和上一帧显示同一个值 —— 那是因为这一帧的动作是"从上一个节点走到当前节点"，画面停在走完之后的位置。dup-start 是"发现重复"的宣告帧，skip 才是真正执行移动的帧，两者职责不同。
再看
1 → 1 → 1 → 2 → 3（头节点就要被删的场景）：
第 5 帧是整题的题眼：
被删的是原来的头节点，而执行删除的是 dummy.next = 2。没有 dummy，这一步根本写不出来。
五、阿里变体：重复的只留一个
面经里的变体是：
保留重复元素只留一个，
1→1→1→2→3→3→4 变成
1→2→3→4。
注意它是"重复过的值留一个、没重复过的值照常留"，不是"每个值都留一个"（后者是 LC 83）。对
1,1,1,2,3,3,4 来说两者恰好结果不同：
改法只有一处：
接回去的时候不要接到 curr，接到重复段的最后一个节点上。
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
last = curr # 记住这一段的最后一个
while curr and curr.val == dup_val:
last = curr # 一路更新，"最后"自然浮出来
curr = curr.next
prev.next = last # ★ 唯一的改动：接 last 而不是 curr
prev = last # prev 也落到这个保留节点上
else:
prev = curr
curr = curr.next
return dummy.next
1→1→1→2→3→3→4 走一遍：三个
1 里留下第三个，
prev 落到它身上；
2 没重复，照常过去；两个
3 里留下第二个；
4 照常留。结果
1 → 2 → 3 → 4。
面试里遇到这种"变体"，先把规则复述一遍再动手。"重复的留一个"和"每个值留一个"听起来像，结果可能一样也可能不一样 —— 拿 1,1,1,2 试一下就知道差别了。主动说出这层区别，比直接写代码得分高。
六、Java 版
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy, curr = head;
while (curr != null) {
if (curr.next != null && curr.val == curr.next.val) {
int dupVal = curr.val;
while (curr != null && curr.val == dupVal) {
curr = curr.next; // 整段跳过
}
prev.next = curr; // 一次摘掉；prev 不动
} else {
prev = curr; // 确认安全，prev 才前进
curr = curr.next;
}
}
return dummy.next;
}
}
Java 里注意
curr.val == curr.next.val 用的是
int 比较，
== 没问题（如果是
Integer 装箱类型就要用
.equals，别踩这个坑）。
七、边界情况
两个"救命"的点值得单独记：
[1,1,2] 验证 dummy 必要性：删除动作落在头节点上，prev 是 dummy。把 dummy 去掉、直接 prev = head 起手，这个用例就会崩。[1,2,2] 验证 内层 while curr and ... 的 curr and：重复段延伸到链表末尾，curr 会走到 None。漏掉这个判断，curr.val 直接 AttributeError（Java 里是 NullPointerException）。
八、复杂度
- 时间
O(n)：外层 while curr 让 curr 从左到右走一遍；内层的 while curr and curr.val == dup_val 也在推同一个 curr，不是嵌套的独立循环 —— 每个节点在整个过程中最多被 curr 访问一次。加起来仍是 O(n)。
- 空间
O(1)：只多了 dummy、prev、curr 三个变量（Java 里还有内层的 dupVal）。没有哈希表、没有递归栈。
那个"内层循环为什么不算嵌套"是很好的加分点。判断方法：看内层循环有没有用到外层之外的独立游标。这里内层推的就是外层的 curr，所以是"同一个指针多走几步"，摊还下来仍是线性。
九、常见坑
1. 忘了 dummy，或者返回了 head。
prev, curr = head, head # 错的！head 自己要被删时无从下手
...
return head # 错的！head 可能已经是孤儿节点
这是这题第一大坑。判断标准很简单：
只要删除动作可能落在头节点上，就必须架 dummy，且返回 dummy.next。
2. prev 在重复时跟着 curr 一起前进了。
if curr.next and curr.val == curr.next.val:
while curr and curr.val == curr.val:
prev = curr # 错的！prev 不该动
curr = curr.next
prev.next = curr
prev 是"接回点"，必须留在重复段的
前一个位置。跟着推进的话，中间几个被摘节点会卡在
prev 和
curr 之间。
3. 内层循环漏掉 curr and。
while curr.val == dup_val: # 错的！重复段到末尾时 curr 变 None，直接崩
必须写成
while curr and curr.val == dup_val。
4. 把重复段的判据写成"值在整条链里出现过"。
seen = set() # 错的！这不是 82 的语义
for node in ...:
if node.val in seen: ...
排序链表上判重
只看邻位就够，不需要统计全局。写成全局统计既慢（要开
O(n) 空间）又容易把 82（全删）和 83（留一个）搞混。
5. 和 LC 83 的条件搞混。
记法：
83 是"踩掉重复的那一个"，82 是"整段铲走"。82 多了一层"先找到段尾"的循环，代码长一点，语义干净得多。
6. 忘了这题不用递归。
递归写链表题很省事，但这题递归要处理的"当前节点是否属于重复段"需要向前看、还要正确回接，写出来比迭代绕得多。而且递归栈是
O(n)，虽然题目没要求
O(1)，但迭代版本来就更短更清晰。
十、面试怎么答
开口 30 秒给思路（别一上来就写代码）：
链表已经排序，所以重复的一定挨在一起，判重只看邻位就行。难点是"重复的节点一个都不留"，意味着重复段的第一个节点也要删 —— 而它可能是头节点，头节点没有前驱。所以先在头上架一个 dummy 当它的人造前驱。然后双指针：prev 是"最后一个确定保留的节点"，curr 往前探。发现 curr.val == curr.next.val 就记住这个值，让 curr 一路跳到重复段之外，再 prev.next = curr 一次把整段摘掉 —— 这一步 prev 不能动。没重复的时候才 prev = curr 一起前进。最后返回 dummy.next。时间 O(n)，空间 O(1)。
然后主动交代三个易错点 —— 这是区分"背过答案"和"真懂"的地方：
- dummy 是为了让"删头节点"变成一次普通删除，返回必须用
dummy.next；
prev 只在确认 curr 不属于重复段时才前进，摘链时它必须停在重复段前面；- 内层循环要写
while curr and curr.val == dup_val，重复段拖到末尾时 curr 会变 None。
追问应对：
- "内层那个 while 不会让复杂度变成 O(n²) 吗？" —— 不会。内外两层推的是同一个
curr，每个节点只被访问一次，摊还是 O(n)。
- "能不用 dummy 吗？" —— 能，但要单独处理"头节点开始的重复段"：先用一个 while 把头部的重复整段删掉，再进入主循环。多一段特判代码，不如 dummy 干净。
- "如果要求重复的留一个呢？" —— 接回的时候接
last（重复段最后一个节点）而不是 curr，其余不变。这就是那个阿里变体。
- "复杂度为什么不是 O(n) 空间？" —— 排序保证重复相邻，所以不需要哈希表统计；全程只有三个指针变量。
- "这题和 LC 83 的区别？" —— 83 每个值留一个（
prev.next = curr.next），82 重复的一个不留（整段跳到段外）。82 多了找段尾的内层循环。
结语
把链表系列串起来看，这题的位置是这样的：
这题最值得带走的东西，不是那 15 行代码，而是这个反射：
看到"可能要删头节点"，先架 dummy。
同样的反射在 LC 19 上是"可能要删头节点"，在 LC 143、234 上是"可能要断开/反转后半段"。链表题的很多麻烦，都是在处理"边界节点没有前驱/没有后继"这类结构缺陷 —— 而
造一个假节点，往往是成本最低的通用解法。
dummy → 1 → 1 → 2
↑
head 没有前驱，删不动；
给它一个 dummy，就删得动了。
下次再遇到"这个操作在头节点上会失效"的链表题，先问自己一句：
能不能在它前面凭空造一个节点？