0203. Remove Linked List Elements ================================= 题目信息 -------- :题号: 0203. 移除链表元素 :难度: Easy :主题: 单链表、指针、虚拟头、节点删除 :原题: `LeetCode 0203 `_ :重点: 把头部和中间节点删除统一为修改“指向当前节点的链接” 题目重述 -------- 给定单链表的头节点 ``head`` 和整数 ``val``,删除所有满足 ``node.val == val`` 的节点,返回删除后的新头节点。未删除节点的相对顺序必须保持不变;目标 节点可以出现在头部、尾部或中间,也可能连续出现。 链表节点数为 ``0`` 到 ``10^4``,节点值位于 ``[1, 50]``,``val`` 位于 ``[0, 50]``。空链表、 全部删除以及原头节点被删除时,都要正确返回新的头节点或空指针。题目只要求重接链表,不要求 复制保留节点。 自建示例 -------- 头部、中间和尾部都有目标值: .. code-block:: text 输入:head = [1, 2, 6, 3, 4, 5, 6],val = 6 输出:[1, 2, 3, 4, 5] 头部连续节点全部被删除: .. code-block:: text 输入:head = [7, 7, 2],val = 7 输出:[2] 空链表或没有匹配值时不需要重接任何真实节点: .. code-block:: text 输入:head = [],val = 3 输出:[] C++ 实现 -------- .. code-block:: cpp 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``: .. code-block:: text 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``: .. list-table:: :header-rows: 1 * - 阶段 - 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`` 成员地址, 它代表前驱的后继链接。于是两种删除都可以写成同一个动作: .. code-block:: text *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`` 也只是普通相等比较,不需要利用节点值的正数范围做特殊分支。