题目描述
思路解析动画文字版
如果链表无序,set 有用。但这里已排序,重复值一定相邻。
cur 指向当前保留节点。若下一个值相同,就跳过下一个;否则 cur 前进。
cur 指向第一个 1:比较 cur 和 cur.next。它们都是 1,发现重复。
跳过第二个 1:把 cur.next 指向下下个节点,第二个 1 被链表绕过去。
cur 仍停在 1:删除后 cur 不前进,因为后面可能还有更多重复值。
1 和 2 不同,前进:当前值 1 和下一个 2 不同,cur 前进到 2。
3 和 3 重复:走到 3 时,再次发现相邻重复,跳过后一个 3。
完成:cur.next 为空,扫描结束,链表变成 1→2→3。
相等就跳,不等才走。
边界三连:空链表、全重复、无重复,覆盖循环条件和删除分支。
雷区实演 · 三个 1:1→1→1 删除第二个 1 后,cur 还要继续和新的 next 比较,不能前进。
面试追问 1:那是 LC82,需要 dummy,因为头节点可能被删除。
面试追问 2:本题保留每个值的第一个节点,不会删除头结点代表的值。
面试追问 3:需要 set 记录已见值,或者排序后再处理。
这题学完不要乱跳,下一步去 对应专题 连刷同类题;卡住时用 AI 答疑追问“为什么这一步成立”,比只背答案更稳。
参考代码
class Solution: def deleteDuplicates(self, head): cur = head while cur and cur.next: if cur.val == cur.next.val: cur.next = cur.next.next else: cur = cur.next return head复杂度
- 时间复杂度:O(n),每个节点最多被检查一次
- 空间复杂度:O(1),只用 cur 指针
可套用的代码模板
这一步不是复读 删除排序链表中的重复元素 的参考答案,而是抽出这题真正能迁移的骨架;换题时先判断状态/容器含义,再填核心分支。
# 链表题先固定三件事:dummy、当前指针、下一跳dummy = ListNode(0)tail = dummywhile 还有节点要处理: nxt = 当前节点.next # 改指针前先存后继 tail.next = 选中的节点 # 只改一根箭头 tail = tail.next # tail 必须跟着走 当前指针 = nxtreturn dummy.next易错点
面试追问把动画讲成自己的话
追问如果要删除所有重复值,一个都不保留呢?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
环形链表
LeetCode 141 · 简单 · 沿着 链表套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题