LeetCode 203简单链表
移除链表元素 图解题解
这道题到底在问什么
给你一个链表的头节点 head 和一个整数 val，请删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。
- 输入
- head = [1,2,6,3,4,5,6], val = 6
- 输出
- [1,2,3,4,5]
- 边界
- head = [] 返回 []；head = [7,7,7,7], val = 7 返回 []。
最优解：一步一步想明白
- 3比如 [7,7,7,7] 全部要删，如果只盯着 head 和 cur，很容易在“新头节点是谁”这件事上绕晕。
- 4不变量：prev 前面的链表已经处理干净；prev.next 是当前要检查的节点。删除时 prev 不动，因为新的 prev.next 还没检查过。
- 5执行：dummy = ListNode(0); dummy.next = head; prev = dummyLeetCode 已经提供 ListNode 定义。我们自己新建 dummy，让它指向原来的 head。现在 prev 站在 dummy，prev.next 就是第一个真实节点 1。
- 6执行：else -> prev = prev.nextprev.next 的值是 1，不等于 val=6，不删。执行 else 分支，让 prev 前进到节点 1。
- 7执行：else -> prev = prev.nextprev.next 的值是 2，也要保留。prev 前面的 1、2 都已经处理干净。
- 8执行：if prev.next.val == val -> prev.next = prev.next.next此时 prev 在节点 2，prev.next 是值为 6 的节点。删除它不是移动 prev，而是让 2.next 直接指向后面的 3。画面里灰掉的 6 表示它已被逻辑删除。
- 9执行：while prev.next 继续删除后 prev 必须留在节点 2，因为新的 prev.next 变成了节点 3，它还没有检查过。连续删除时这一步尤其关键。
- 10执行：else 分支连续三次3、4、5 都不等于 6，所以每次走 else，prev 依次前进。现在 prev 在节点 5，prev.next 指向尾部的 6。
- 11执行：prev.next = prev.next.next尾部 6 也要删除。执行 prev.next = prev.next.next，此时 prev.next.next 是 None，所以节点 5 会直接指向空。灰掉的尾部 6 已不在结果链表里。
- 12执行：while prev.next 结束prev.next 已经为空，说明后面没有节点可检查。链表中所有等于 6 的节点都被跳过了。
- 13执行：return dummy.next最后返回 dummy.next。即使原 head 被删除，dummy.next 也会指向新的头节点；这个样例里新头仍然是 1。
- 16这题的可迁移点是“站在前一个节点删后一个节点”。凡是链表删除、插入、拼接，都先想谁能安全改 next。
⚠️ 容易写错的地方
✗ 错：直接从 head 开始删，单独处理很多头节点情况
✓ 对：使用 dummy 统一逻辑
head 自己可能要被删除，甚至整条链表都被删除。
✗ 错：删除节点后立刻 prev = prev.next
✓ 对：删除时 prev 不动
新的 prev.next 还没检查，连续 val 会被跳过。
✗ 错：返回 head
✓ 对：返回 dummy.next
原 head 可能已经被删除，新头节点要从 dummy.next 取。
完整代码（Python）
Python
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 两个指针。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 移除链表元素 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「链表」，换最直接的暴力解会差在哪？+
链表抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。