题目描述
思路解析动画文字版
比如 [7,7,7,7] 全部要删,如果只盯着 head 和 cur,很容易在“新头节点是谁”这件事上绕晕。
不变量:prev 前面的链表已经处理干净;prev.next 是当前要检查的节点。删除时 prev 不动,因为新的 prev.next 还没检查过。
初始化:dummy 接到 head 前面:LeetCode 已经提供 ListNode 定义。我们自己新建 dummy,让它指向原来的 head。现在 prev 站在 dummy,prev.next 就是第一个真实节点 1。
检查 1:不等于 6,prev 前进:prev.next 的值是 1,不等于 val=6,不删。执行 else 分支,让 prev 前进到节点 1。
检查 2:不等于 6,继续前进:prev.next 的值是 2,也要保留。prev 前面的 1、2 都已经处理干净。
检查第一个 6:命中 val,改 prev.next:此时 prev 在节点 2,prev.next 是值为 6 的节点。删除它不是移动 prev,而是让 2.next 直接指向后面的 3。画面里灰掉的 6 表示它已被逻辑删除。
删除后 prev 不动:继续检查新的 prev.next:删除后 prev 必须留在节点 2,因为新的 prev.next 变成了节点 3,它还没有检查过。连续删除时这一步尤其关键。
检查 3、4、5:都保留,prev 逐步前进:3、4、5 都不等于 6,所以每次走 else,prev 依次前进。现在 prev 在节点 5,prev.next 指向尾部的 6。
检查尾部 6:再次命中,删除尾节点:尾部 6 也要删除。执行 prev.next = prev.next.next,此时 prev.next.next 是 None,所以节点 5 会直接指向空。灰掉的尾部 6 已不在结果链表里。
循环结束:prev.next 为空:prev.next 已经为空,说明后面没有节点可检查。链表中所有等于 6 的节点都被跳过了。
返回 dummy.next:新的头节点仍是 1:最后返回 dummy.next。即使原 head 被删除,dummy.next 也会指向新的头节点;这个样例里新头仍然是 1。
这题的可迁移点是“站在前一个节点删后一个节点”。凡是链表删除、插入、拼接,都先想谁能安全改 next。
参考代码
class Solution: def removeElements(self, head, val): dummy = ListNode(0) dummy.next = head prev = dummy while prev.next: if prev.next.val == val: prev.next = prev.next.next else: prev = prev.next return dummy.next复杂度
- 时间复杂度:O(n),每个节点最多被检查一次。
- 空间复杂度:O(1),只使用 dummy 和 prev 两个指针。
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
反转链表
LeetCode 206 · 简单 · 沿着 链表套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题