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

一列已经排好序的链表车厢，只保留每个编号的第一节。

把链表想象成一列按编号排好序的「数据列车」。重复车厢一定相邻——扫描器 cur 站在当前车厢上，若与下一节编号相同，就执行 cur.Next = cur.Next.Next 改指针绕过重复节点，而不是「删除值」。

链表有序去重单指针原地改 next时间 O(n)空间 O(1)

核心公式

if cur.Val == cur.Next.Val:
    cur.Next = cur.Next.Next
else:
    cur = cur.Next

切换测试用例

预期输出：1 → 2 → 3 → nil

Step 1/15题目输入

Step 1题目输入

Step 1：题目输入

这是一列已经按编号升序排好的数据列车：1 → 1 → 2 → 3 → 3 → nil。因为链表有序，重复值一定相邻出现——我们只需要比较 cur 和 cur.Next，不需要 HashSet。

cur / next 高亮 Duplicate 新 next 电弧 detached

执行状态

cur: cur 尚未初始化
cur.Next: cur.Next → nil
判断条件: 有序链表，重复必相邻
执行动作: 展示输入链表
当前链表: 1 → 1 → 2 → 3 → 3 → nil

不变量

cur 之前的链表段已经完成去重，并且每个值只保留第一次出现的节点。

Go 代码同步

1func deleteDuplicates(head *ListNode) *ListNode {
2    cur := head
3 
4    for cur != nil && cur.Next != nil {
5        if cur.Val == cur.Next.Val {
6            cur.Next = cur.Next.Next
7        } else {
8            cur = cur.Next
9        }
10    }
11 
12    return head
13}

复杂度 · 时间 O(n) · 空间 O(1)

为什么有序很重要？

因为链表已排序，重复值一定连续出现。我们只需要比较当前节点和下一个节点，不需要 HashSet。

为什么不需要 dummy？

LC83 每个重复值至少保留一个，删除的是 cur.Next，不会删除 head 本身，所以不需要 dummy。但 LC82 需要 dummy，因为 LC82 要把所有重复值都删掉，head 可能被删除。

为什么删除后不能移动 cur？

因为可能出现 1 → 1 → 1 → 2。删除一个重复 1 后，cur.Next 仍可能是 1，所以必须继续检查新的 cur.Next。

LC83 vs LC82 对比

LC83 · 重复值保留一个

输入：1 → 1 → 2 → 3 → 3

输出：1 → 2 → 3

压缩重复段，只留段首

LC82 · 重复值全部删除

输入：1 → 1 → 2 → 3 → 3

输出：2

发现重复段，整段删除