0203. Remove Linked List Elements¶
题目信息¶
- 题号:
移除链表元素
- 难度:
Easy
- 主题:
单链表、指针、虚拟头、节点删除
- 原题:
- 重点:
把头部和中间节点删除统一为修改“指向当前节点的链接”
题目重述¶
给定单链表的头节点 head 和整数 val,删除所有满足
node.val == val 的节点,返回删除后的新头节点。未删除节点的相对顺序必须保持不变;目标
节点可以出现在头部、尾部或中间,也可能连续出现。
链表节点数为 0 到 10^4,节点值位于 [1, 50],val 位于 [0, 50]。空链表、
全部删除以及原头节点被删除时,都要正确返回新的头节点或空指针。题目只要求重接链表,不要求
复制保留节点。
自建示例¶
头部、中间和尾部都有目标值:
输入:head = [1, 2, 6, 3, 4, 5, 6],val = 6
输出:[1, 2, 3, 4, 5]
头部连续节点全部被删除:
输入:head = [7, 7, 2],val = 7
输出:[2]
空链表或没有匹配值时不需要重接任何真实节点:
输入:head = [],val = 3
输出:[]
C++ 实现¶
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
return removeWithDummy(head, val);
}
private:
ListNode* removeWithDummy(ListNode* head, int val) {
ListNode dummy(0);
dummy.next = head;
ListNode* previous = &dummy;
while (previous->next != nullptr) {
if (previous->next->val == val) {
previous->next = previous->next->next;
} else {
previous = previous->next;
}
}
return dummy.next;
}
ListNode* removeWithLinkSlot(ListNode* head, int val) {
ListNode** link = &head;
while (*link != nullptr) {
if ((*link)->val == val) {
*link = (*link)->next;
} else {
link = &(*link)->next;
}
}
return head;
}
};
题解¶
删除的对象其实是一个链接¶
单链表节点只有 next,删除当前节点不能从当前节点本身向前找到前驱;真正需要修改的是
“指向当前节点的那个链接”。如果当前节点在中间,这个链接是前驱的 next;如果当前节点是
头节点,这个链接是外部变量 head。删除动作本身始终相同:让这个链接跳过当前节点,直接
指向它的后继。
最直观的两段式写法会先循环处理头部目标节点,再从某个前驱开始处理主体。它能够覆盖情况,
但头部连续删除和中间删除被拆成两套边界逻辑;若只删除一次头节点,[val, val, x] 就会
留下一个错误的头节点。我们需要让头节点也拥有一个“前驱链接”。
虚拟头统一删除分支¶
在真实头部之前放置一个不参与结果的 dummy:
dummy -> head -> ...
此后原头节点和所有中间节点都统一由某个前驱的 next 指向。维护 previous 作为已确认
保留前缀的最后节点,当前候选固定为 previous->next:
候选值等于
val:把previous->next改为候选的后继,previous不移动;候选值不等于
val:候选必须保留,previous移到候选。
删除后不移动前驱是关键。因为候选的后继可能仍然匹配,前驱必须继续检查同一个链接槽位;只有 保留分支才会让已确认前缀向后扩展。
循环不变量¶
每轮开始时保持:
从
dummy.next到previous的节点都已检查,且值都不等于val;这段已保留前缀仍按原链表顺序连接;
previous->next是尚未检查后缀的第一个节点,或为空;已删除节点已从
dummy.next不可达,未检查后缀没有丢失。
若候选匹配,重接后它从返回链路中消失,后继成为新的候选,不变量继续成立;若候选不匹配, 前驱移动到它,已保留前缀扩大一个节点,不变量也继续成立。每轮都让一个节点永久离开未检查 后缀,因此节点最多检查一次。
状态走读¶
对 1 -> 6a -> 6b -> 3、val = 6:
阶段 |
previous |
candidate |
链接变化 |
|---|---|---|---|
初始 |
|
|
尚未修改 |
保留 1 |
|
|
previous 前进 |
删除 6a |
|
|
|
删除 6b |
|
|
|
保留 3 |
|
空 |
循环结束 |
头部连续删除时,previous 始终停在 dummy:先跳过第一个目标节点,再检查新的
dummy.next,所以 [7, 7, 2] 不需要特殊循环。若每个节点都匹配,dummy.next 最后为
空;若输入本来为空,第一次条件检查就结束。
指针槽位的替代方案¶
removeWithLinkSlot 不创建虚拟节点,而是让 link 指向“当前链接槽位”的地址:开始时
link = &head,它代表外部头指针;保留一个节点后,link 移到该节点的 next 成员地址,
它代表前驱的后继链接。于是两种删除都可以写成同一个动作:
*link = (*link)->next
这正是把“指向当前节点的链接”直接作为状态保存。它同样是 O(1) 空间,但二级指针比虚拟头
更难在走读时建立直觉;公共入口选择虚拟头版本,保留指针槽位版本作为真正改变状态表达的替代
方法。
代码分析¶
ListNode dummy(0) 只在栈上存在,返回的是 dummy.next,不会把虚拟节点混进结果。主循环
从 previous->next 读取候选,删除分支只改一条 next,不复制节点,也不主动 delete:
在线评测通常不声明函数拥有输入节点的释放权,函数只负责返回链路。实际工程若明确由本函数接管
所有权,才应在保存后继并完成重接后释放被移除节点。
removeWithLinkSlot 的 link 不是当前节点指针,而是保存当前节点地址的指针。删除时改写
*link;保留时把 link 推进到当前节点的 next 槽位。这解释了为什么它可以同时处理原头
节点和中间节点,也解释了为什么主解使用虚拟头更易读。
复杂度与边界¶
每个原节点至多被检查一次,两个版本的时间复杂度都是 O(n),额外空间都是 O(1)。保留
节点的相对顺序没有改变,结果复用原节点,不创建与 n 成正比的新链表。
空链表直接返回空指针;头部连续匹配时前驱不前进;尾部匹配由跳过节点后的空 next 结束;
val 为 0 也只是普通相等比较,不需要利用节点值的正数范围做特殊分支。