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

• LeetCode：原题
• 难度：简单
• 归类：链表
• 主解法：单指针一次遍历

#题目描述

给定一个已按升序排列的链表，删除所有重复元素，使每个元素只出现一次，并返回同样按升序排列的结果链表。

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

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

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

• 本题为每个值保留一个节点，例如 [1,1,2] 变为 [1,2]。
• 第 82 题会删除所有出现过重复的值，因此 [1,1,2] 变为 [2]。

#核心思路

链表已经有序，所以值相同的节点一定连续出现。使用指针 cur 检查当前节点与下一个节点：

• 如果 cur.val === cur.next.val，说明 cur.next 是多余的重复节点，令 cur.next = cur.next.next 将其删除。
• 如果二者值不同，说明当前值已经去重完毕，令 cur = cur.next，开始处理下一个值。

关键点是：删除重复节点后不能立即移动 cur。同一个值可能连续出现三次以上，需要继续用 cur 与新的 cur.next 比较。

#指针含义与不变量

cur 始终指向当前需要保留的节点。

每轮循环开始时：

1. 从 head 到 cur 的链表已经完成去重。
2. 已处理部分保持原有顺序，每个值只保留一个节点。
3. cur.next 及其后面的节点尚未完全处理。

若 cur.next 与 cur 相同，删除 cur.next 后不变量仍然成立；若二者不同，cur.next 是下一个需要保留的值，将 cur 移到该节点后不变量同样成立。

#示例推演

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

此时 cur.next === null，遍历结束，返回 [1,2,3]。

#代码实现

参考实现来源：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) {
    let cur = head;

    while (cur && cur.next) {
        if (cur.val === cur.next.val) {
            // 删除重复节点后不移动 cur，继续检查新的 cur.next。
            cur.next = cur.next.next;
        } else {
            // 当前值已经处理完，开始处理下一个值。
            cur = cur.next;
        }
    }

    return head;
};

#为什么不需要哑节点

本题只删除重复值中的多余节点，第一次出现的节点一定保留，所以原来的头节点不会被删除。直接返回 head 即可。

第 82 题可能删除包含头节点的整个重复段，因此需要使用哑节点统一处理头部删除逻辑。

#正确性证明

根据循环不变量证明：

• 初始化：cur = head。若链表非空，从 head 到 cur 只有一个节点，显然已经去重。
• 保持：
  • 若 cur.val === cur.next.val，算法删除后一个节点。它与 cur 的值相同，删除它不会改变结果中应保留的值，cur 之前的部分也不受影响。
  • 若二者不同，由于链表有序，cur 对应的值不可能在后面再次出现，因此可以安全地移动到 cur.next。
• 终止：当 cur === null 或 cur.next === null 时，没有待比较的后继节点。根据不变量，从 head 到链表末尾已经全部去重。

因此算法能正确保留每个值的第一个节点，并删除其余重复节点。

#复杂度分析

• 时间复杂度：O(n)。指针只会向后移动，每个节点至多被检查或删除一次。
• 空间复杂度：O(1)。算法只使用一个额外指针，并原地修改链表。

#边界情况

• 空链表 []：返回 []。
• 单节点 [1]：返回 [1]。
• 没有重复值 [1,2,3]：返回原链表。
• 所有值相同 [1,1,1]：返回 [1]。
• 重复值位于头部 [1,1,2]：返回 [1,2]。
• 重复值位于尾部 [1,2,2]：返回 [1,2]。
• 存在多个重复段 [1,1,2,3,3]：返回 [1,2,3]。

#常见错误

#删除重复节点后仍然移动 cur

对于 [1,1,1]，删除第二个 1 后，如果立即移动 cur，就可能漏掉第三个 1。删除操作后应保持 cur 不动，继续检查新的后继节点。

#把整个重复段全部删除

本题要求每个值保留一个节点。删除整个重复段实现的是第 82 题，而不是本题。

#忽略空链表

循环条件必须先判断 cur，再访问 cur.next。JavaScript 的短路求值保证 cur === null 时不会继续读取属性。

#误以为必须使用哈希表

有序性保证重复值相邻，局部比较即可完成去重，不需要额外记录已经出现过的值。

#面试官递进追问

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

有序保证相同值连续出现。只要相邻节点值不同，就能确定当前值不会在后面再次出现。

#2. cur 指针表示什么？

cur 指向当前值需要保留的那个节点；cur 之前的链表已经完成去重。

#3. 为什么删除重复节点后不能移动 cur？

相同值可能连续出现三次以上。删除 cur.next 后，需要继续比较 cur 与新的 cur.next，直到后继节点的值发生变化。

#4. 为什么本题不需要哑节点？

每个值都需要保留一个节点，因此原头节点一定不会被删除，不存在更新链表头的特殊情况。

#5. 这个实现修改了原链表吗？

修改了。算法通过调整 next 指针原地删除节点。如果要求保留原链表，需要创建新节点，额外空间会变为 O(n)。

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

若要保留每个值第一次出现的节点，可以用哈希集合记录已出现值，时间复杂度为 O(n)，空间复杂度为 O(n)。也可以先排序，但会改变原有顺序。

#7. 时间复杂度为什么是 O(n)？

cur 和链表中的连接只向后推进，每个节点至多被保留后经过一次，或作为重复节点删除一次，所以总操作次数与节点数成正比。

#8. 能否使用递归实现？

可以，但最坏递归深度为 O(n)，需要 O(n) 调用栈。迭代实现更直接，并且额外空间为 O(1)。

#可迁移总结

• 有序链表去重只需比较相邻节点。
• 删除后继节点时，当前指针通常不移动，因为新的后继节点仍需检查。
• 当头节点一定保留时，不需要哑节点；当头节点可能被删除时，哑节点能统一边界逻辑。
• 原地修改 next 指针可以实现 O(1) 额外空间。

#刷题后自测

1. 为什么 [1,1,1] 能检验“删除后不能移动 cur”这一关键点？
2. 本题为什么可以直接返回 head，而第 82 题通常返回 dummy.next？
3. 如果不能修改输入链表，应该怎样实现？