0203. Remove Linked List Elements

题目信息

题号:
  1. 移除链表元素

难度:

Easy

主题:

单链表、指针、虚拟头、节点删除

原题:

LeetCode 0203

重点:

把头部和中间节点删除统一为修改“指向当前节点的链接”

题目重述

给定单链表的头节点 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

链接变化

初始

dummy

1

尚未修改

保留 1

1

6a

previous 前进

删除 6a

1

6b

1.next 越过 6a

删除 6b

1

3

1.next 越过 6b

保留 3

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 也只是普通相等比较,不需要利用节点值的正数范围做特殊分支。