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

题目描述

已排序链表，删除重复元素使每个值只保留一个。

思路解析

cur 从头走。如果 cur.val == cur.next.val，说明 cur.next 是重复的，让 cur.next 指向 cur.next.next 把它摘掉（cur 不动，继续比）；不同则 cur 前进。

起点 · cur=头：cur 指向第一个 1。比较它和下一个节点。

cur=1, next 也是 1 · 重复：cur(1) 和 cur.next(1) 相同！cur.next 这个重复的 1(del)要被摘掉。

跳过重复 · cur 不动：执行 cur.next = cur.next.next：摘掉重复的 1（虚线划掉），cur 的箭头越过它接到 2。cur 不前进——还要拿它和新的下一个(2)继续比。

cur=1, next=2 · 不同 → 前进：现在 cur(1) 和下一个 2 不同，保留。cur 前进到 2，继续比较。

cur=2, next=3 · 不同 → 前进：2 和 3 不同，cur 前进到 3（第一个 3）。

cur=3, next 也是 3 · 跳过：3 和下一个 3 相同，摘掉重复的 3（虚线划掉）。cur 不动，它的 next 现在是 null。

完成 · 1 → 2 → 3：cur.next 是 null，遍历结束。保留下来的是 1 → 2 → 3，每个值只剩一个。

链表删除的通用细节：摘掉一个节点后当前指针别动，因为新接上的下一个可能仍要处理。前进只发生在「不删」时。

参考代码（Python）

1cur = head
2while cur and cur.next:
3    if cur.next.val == cur.val:       # 重复
4        cur.next = cur.next.next      # 跳过，cur 不动
5    else:
6        cur = cur.next                # 不同才前进
7return head

复杂度分析

• 时间复杂度：O(n) —— 一趟扫描
• 空间复杂度：O(1) —— 原地修改

套路模板

记住骨架：删除时只改指针、不前进；保留时才前进。这个「删/不删决定动不动」是链表删除题的统一节奏。

1cur = head
2while cur and cur.next:
3    if 该删(cur.next):
4        cur.next = cur.next.next      # 删除，cur 不动
5    else:
6        cur = cur.next                # 保留才前进

易错点

• ❌ 删除后还 cur = cur.next → ✅ 删除时 cur 保持不动（新接上的节点可能还和 cur 重复，会漏删）
• ❌ 循环忘判 cur.next → ✅ while cur and cur.next（访问 cur.next.val 前必须确保 cur.next 存在）

以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。