题目描述
思路解析动画文字版
「相同就跳过、不同才前进」——因为已排序,跳过的一定是和 cur 重复的那个。
cur 停在头节点 1,先把它确认保留(标绿)。接下来反复比较 cur 和它后面的节点,决定「摘掉重复」还是「前进」。
看 cur=1 和它后面的 next=1:两个都是 1,相等 → 这是重复,下一帧把 next 摘掉。
执行 cur.next = cur.next.next:把重复节点 1 摘掉(变灰、两侧箭头断开 ·),cur 留在 1 不动,继续和再后面的节点比。
看 cur=1 和它后面的 next=2:1 和 2 不相等 → cur 这个值处理完了,下一帧 cur 前进。
执行 cur = cur.next:cur 前进一格到 2,开始处理这个新值。前面 已确认保留的节点变绿。
看 cur=2 和它后面的 next=2:两个都是 2,相等 → 这是重复,下一帧把 next 摘掉。
执行 cur.next = cur.next.next:把重复节点 2 摘掉(变灰、两侧箭头断开 ·),cur 留在 2 不动,继续和再后面的节点比。
看 cur=2 和它后面的 next=3:2 和 3 不相等 → cur 这个值处理完了,下一帧 cur 前进。
执行 cur = cur.next:cur 前进一格到 3,开始处理这个新值。前面 已确认保留的节点变绿。
看 cur=3 和它后面的 next=4:3 和 4 不相等 → cur 这个值处理完了,下一帧 cur 前进。
执行 cur = cur.next:cur 前进一格到 4,开始处理这个新值。前面 已确认保留的节点变绿。
看 cur=4 和它后面的 next=4:两个都是 4,相等 → 这是重复,下一帧把 next 摘掉。
执行 cur.next = cur.next.next:把重复节点 4 摘掉(变灰、两侧箭头断开 ·),cur 留在 4 不动,继续和再后面的节点比。
看 cur=4 和它后面的 next=5:4 和 5 不相等 → cur 这个值处理完了,下一帧 cur 前进。
执行 cur = cur.next:cur 前进一格到 5,开始处理这个新值。前面 已确认保留的节点变绿。
看 cur=5 和它后面的 next=6:5 和 6 不相等 → cur 这个值处理完了,下一帧 cur 前进。
执行 cur = cur.next:cur 前进一格到 6,开始处理这个新值。前面 已确认保留的节点变绿。
cur 走到最后一个存活节点 6,后面没有节点了,结束。灰掉的都是重复副本,剩下的绿色节点 1→2→3→4→5→6 就是答案,每个值只出现一次。
空 / 单节点 / 全相同三种边界,代码天然覆盖,不需要特判。
两个高频追问:LC82 是「一个不留」的进阶版,思路从「留一个」变「整段删」。
参考代码
def deleteDuplicates(head): cur = head while cur and cur.next: if cur.next.val == cur.val: cur.next = cur.next.next # 摘掉重复,cur 不动 else: cur = cur.next # 不同才前进 return head复杂度
- 时间:O(n),cur 把每个节点最多经过一遍
- 空间:O(1),只用一个指针,原地改 next,不开额外结构
易错点
面试追问把动画讲成自己的话
追问如果要求重复的全部删掉、一个都不留(LC82)怎么改?
追问链表没排序还能 O(n) 去重吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
环形链表
LeetCode 141 · 简单 · 沿着 链表套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题