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

很多人会和 LC83「删除重复元素」搞混：那题重复值留一个，这题重复值全删光。差一个字，写法完全不同。

头节点本身可能就是重复值要被删（如 1→1→2）。在最前面焊一个永不被删的哑节点 dummy，让 prev 有稳定落脚点，cur 去往后探路。最后返回 dummy.next。

焊上哑节点：最左边的 D 就是哑节点 dummy。prev 先站在 dummy 上，因为 dummy 一定保留。

cur 从真头出发：cur 指向第一个真节点 1。比较 cur(1) 和它的下一个 cur.next(2) 是否相等。

1 ≠ 2 · 1 是独苗：1 和 2 不相等，说明 1 是独苗、确定保留（标绿）。该让 prev 跟上来了。

prev、cur 同时前移：prev 前移到 1，cur 前移到 2。再比较 cur(2) 和 cur.next(3)。

2 ≠ 3 · 2 是独苗：2 和 3 也不相等，2 同样是独苗，保留（标绿）。注意：下面要起波澜了。

prev、cur 再前移：prev 移到 2，cur 移到第一个 3。比较 cur(3) 和 cur.next(3)。

cur=3 · cur.next=3 相等！：cur(3) 和 cur.next(3) 相等！发现重复值 3。这时一个 3 都不能留，先把第一个 3 标红（待删），记下值 3，让 cur 往后吃。

cur 吃掉第 2 个 3：内层小循环：只要 cur 的值还是 3，cur 就往后走。cur 走到第二个 3，它也标红待删。

cur 吃掉第 3 个 3：值还是 3，继续走。cur 走到第三个 3，三个 3 全部标红，都将被删掉。

cur 走出 3 的区间：cur 再往后，现在指向 4，值不再是 3，内层循环停。此刻三个 3 都夹在 prev(2) 和 cur(4) 之间，等着被一刀切掉。

整段删除 · prev.next = cur：关键一刀：让 prev.next 直接指向 cur。2 后面直接接 4，三个 3 被整段绕过、彻底从链表消失。注意 prev 没有前移——它还要继续盯下一段。

cur=4 · cur.next=4 又相等：再看 cur(4) 和 cur.next(4)，又相等！重复值 4 出现。同样套路：把所有 4 全删，先把第一个 4 标红。

cur 吃掉第 2 个 4：cur 继续往后吞，走到第二个 4，它也标红。两个 4 都待删。

cur 走出 4 的区间：cur 走到 5，值不是 4 了，停。两个 4 都标红，又夹在 prev(2) 和 cur(5) 之间。

再来一刀 · prev.next = cur：再让 prev.next 指向 cur，2 后面直接接 5，两个 4 整段消失。现在链表是 D→1→2→5，cur 指向 5，prev 仍不动。

cur=5 · cur.next=null：cur(5) 后面是 null，没有下一个可比，说明 5 不重复、保留（标绿）。这一支走 else 分支，prev 和 cur 都要前移。

prev 前移到 5，cur 走向 null：prev 前移到 5，cur 走到 null（已离开链表，不再显示）。外层 while 的条件不再满足。

循环结束 · 返回 dummy.next：cur 已为 null，循环结束。返回 dummy.next，也就是 1→2→5，正是答案。哑节点 D 完成使命，可以丢掉了。

一句话记住：prev 永远停在「确定要留」的节点上；cur 去前面探路，一旦发现重复就把那一整片同值节点全部跳掉。

雷区实演 · 开头就重复：输入 1→1→2：开头两个 1 都要删。多亏有哑节点 D，prev 稳站在 D 上，删完后 D.next 直接指向 2，结果是 2。要是没 dummy，头被删了根本不知道该返回谁。

雷区实演 · 全部重复：输入 1→1→1：三个 1 全是重复，整段删光，链表变空。dummy.next 指向 null，返回空链表。算法天然处理这种极端情况。

边界三连：空链表、整段全删、完全无重复——这三种都不会让代码出错，dummy + 双指针的写法把它们一视同仁地处理掉。

面试追问 1：面试最爱拿这两道对比。核心区别一句话：留不留那一个。

面试追问 2：prev 动不动是这题最容易写错的点：只有「不重复」分支才前移 prev。

面试追问 3：「已排序」是这题的关键前提，让相同的值聚在一起，才能一段一段地处理。

这题学完别乱跳，去 链表专题 连刷同类题；卡住时可以随时在页面里提问「为什么这一步成立」，比只背答案更稳。