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

• LeetCode：原题
• 难度：中等
• 归类：链表、双指针
• 主解法：哑节点 + 一次遍历

#题目描述

给定一个已按升序排列的链表，删除链表中所有存在重复数字的节点，只保留原链表中只出现一次的数字，并返回结果链表。

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

输入：head = [1,1,1,2,3]
输出：[2,3]

注意本题与 83. 删除排序链表中的重复元素 的区别：

• 第 83 题会为每个值保留一个节点。
• 本题会删除所有出现过重复的值。例如 [1,1,2] 的结果是 [2]，而不是 [1,2]。

#核心思路

链表已经有序，因此值相同的节点一定连续出现。可以使用快慢指针判断从 fast 开始的连续段是否包含多个节点：

• 若 fast.next 与 fast 的值不同，fast 只出现一次，可以保留，并让 slow 前进到 fast。
• 若值相同，就让 fast 移到这段重复值的最后一个节点，再令 slow.next = fast.next，一次性删除整段。

这里的“快慢”描述的是职责不同，而不是两个指针始终按固定速度移动：

• slow：慢指针，指向结果链表已确认部分的最后一个节点。
• fast：快指针，用于扫描当前连续段，并最终停在该段的最后一个节点。

由于链表头节点本身也可能属于重复段，例如 [1,1,2]，需要创建哑节点 dummy。这样删除头部重复段与删除中间重复段可以使用同一套逻辑。

#不变量

每轮外层循环开始时：

1. dummy 到 slow 的链路已经处理完毕，其中所有节点在原链表中都只出现一次。
2. slow.next === fast，fast 是尚未处理部分的第一个节点。

处理 fast 所在的连续段后：

• 如果该段长度为 1，保留它并令 slow = fast。
• 如果该段长度大于 1，令 slow.next 跳过整段，slow 保持不动。

两种情况都会重新建立不变量。

#示例推演

以 head = [1,2,3,3,4,4,5] 为例：

最终返回 dummy.next，得到 [1,2,5]。

#代码实现

参考实现来源：doocs/leetcode，按本文结构重新整理；原项目采用 CC BY-SA 4.0。

#JavaScript 实现

/**
 * function ListNode(val, next) {
 *     this.val = val ?? 0;
 *     this.next = next ?? null;
 * }
 *
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    const dummy = new ListNode(0, head);
    let slow = dummy;
    let fast = head;

    while (fast) {
        // 快指针移到当前连续值的最后一个节点。
        while (fast.next && fast.val === fast.next.val) {
            fast = fast.next;
        }

        if (slow.next === fast) {
            // fast 没有在连续段内移动，说明当前值只出现一次。
            slow = fast;
        } else {
            // slow.next 到 fast 是一整段重复值，全部删除。
            slow.next = fast.next;
        }

        fast = fast.next;
    }

    return dummy.next;
};

#为什么 slow.next === fast 能判断是否重复

进入一轮循环时，slow.next 和 fast 指向同一个节点。

• 如果内层循环一次都没有执行，fast 没有移动，所以 slow.next === fast，当前值只出现一次。
• 如果内层循环执行过，fast 已经移到重复段末尾，所以 slow.next !== fast，从 slow.next 到 fast 的节点都必须删除。

这个判断省去了额外的布尔变量或计数器。

#正确性证明

按照链表中连续值的分组进行归纳。

• 初始化：slow = dummy、fast = head。此时已处理部分为空，不变量成立。
• 保持：若当前组只有一个节点，算法保留该节点并移动 slow；若当前组有多个节点，算法让 slow.next 越过整组。由于链表有序，同一个值不可能在后面再次出现，因此对当前组的处理是完整且正确的。
• 终止：当 fast === null 时，所有连续组都已处理。重复组均被删除，单节点组均被保留，所以 dummy.next 正是只含原链表中不重复值的结果链表。

因此算法正确。

#复杂度分析

• 时间复杂度：O(n)。虽然代码包含嵌套循环，但每个节点最多被 fast 访问一次。
• 空间复杂度：O(1)。只使用了常数个指针；哑节点也只占常数空间。

#边界情况

• 空链表 []：返回 []。
• 单节点 [1]：返回 [1]。
• 所有节点都重复 [1,1,1]：返回 []。
• 重复段位于头部 [1,1,2,3]：返回 [2,3]。
• 重复段位于尾部 [1,2,3,3]：返回 [1,2]。
• 多个相邻重复段 [1,1,2,2,3]：返回 [3]。

#常见错误

#只删除重复段中的多余节点

这种写法得到的是第 83 题的结果。以 [1,1,2] 为例，本题必须删除两个 1，而不是保留一个。

#发现重复后只跳过一个节点

重复值可能出现两次以上。必须先找到整段重复值的末尾，再整体断链。

#不使用哑节点

并非不能实现，但当头部就是重复段时需要额外更新 head，会增加分支和出错概率。

#删除重复段后错误地移动 slow

删除重复段后，slow 仍应指向已确认结果的最后一个节点。只有保留当前节点时才移动 slow。

#面试官递进追问

#1. 为什么有序是关键条件？

有序保证相同值连续出现。处理完一个连续段后，便能确定这个值是否应被保留；如果链表无序，相同值可能出现在后面，单次局部扫描无法作出最终判断。

#2. slow 和 fast 分别表示什么？

slow 指向已确认保留部分的最后一个节点，fast 用于扫描当前连续段。扫描重复段时只有 fast 移动；确认当前段只出现一次后，slow 才会前进。

#3. 为什么需要哑节点？

头节点可能属于需要删除的重复段。哑节点为头节点提供一个稳定的前驱，使删除头部、中间和尾部重复段都能通过修改 slow.next 完成。

#4. slow.next === fast 为什么表示当前值没有重复？

一轮开始时二者指向同一节点。只有发现相邻节点值相等时，内层循环才会移动 fast；因此循环结束后二者仍相等，恰好说明内层循环没有执行，当前连续段长度为 1。

#5. 删除重复段后为什么不能移动 slow？

重复段中没有任何节点可以进入结果链表，slow 仍然是已确认保留部分的最后一个节点。此时只应修改 slow.next，让它指向下一个待处理节点。

#6. 嵌套循环为什么仍是 O(n)？

内外层循环共享并单向推进同一个 fast 指针。每个节点只会被经过一次，总访问次数与链表长度成正比，并不是对每个节点都重新扫描整个链表。

#7. 如果链表无序怎么办？

可以先用哈希表统计每个值的出现次数，再遍历链表删除出现次数大于 1 的节点，时间复杂度为 O(n)，空间复杂度为 O(n)。若允许改变节点顺序，也可以先排序，但链表排序通常需要 O(n log n) 时间。

#8. 能否使用递归？

可以按连续段递归处理后续链表，但递归深度最坏为 O(n)，会占用 O(n) 调用栈；迭代解法空间更优。

#可迁移总结

• 有序数据中的相同元素会形成连续段，可以按段处理。
• 当链表头可能被删除时，优先考虑哑节点统一边界逻辑。
• 慢指针应始终停在“已确认保留部分”的末尾；删除节点时通常不移动慢指针。
• 嵌套循环不一定意味着 O(n²)，关键要看每个元素总共被访问多少次。

#刷题后自测

1. 为什么删除重复段后不能移动 slow？
2. slow.next === fast 为什么能准确区分单节点段和重复段？
3. 如果输入不是有序链表，需要怎样修改算法？