LeetCode 203. 移除链表元素

2021-08-20 HGNULB 约 7 分钟

文章信息 10 个分类 2 个标签

分类

LeetCode CodeTop 简单已解决已掌握 2-5 美团阿里巴巴快手滴滴

题目描述

✅ 203. 移除链表元素

题意分析

给一条单链表的头节点和一个整数 val，把链表里所有值等于 val 的节点全部摘掉，返回处理后的头节点。

有两个信号决定了写法的形状。第一，要删的是「所有」而不是「第一个」，所以不能找到就收工；而且待删节点可能连续成片，删完一个之后紧跟着的仍可能是待删节点。第二，返回类型是链表头而不是 void，这在提醒头节点本身可能被删，甚至可能被连删好几个——极端情况下整条链被清空，答案是空链表。

从操作层面看，单链表摘除一个节点只能借助它的前驱：把前驱的 next 指向被删节点的后继。所以遍历时真正该盯住的是「当前节点的后继」，而不是当前节点自己。

边界要单独想清楚四种：链表本身为空；头节点就是待删值；开头连续多个都是待删值；整条链的值全等于 val。这四种都要落到同一段逻辑里，不该各写一支。

解法：虚拟头节点迭代删除

核心思路

朴素写法会分成两段：先用一个 while (head != null && head.val == val) head = head.next; 剥掉开头的连续待删节点，再从新的 head 出发处理中间部分。这能过，但两段逻辑近乎重复，而且第一段循环的判空条件很容易写漏，链表被删空时还要额外照顾返回值。瓶颈在于「头节点没有前驱」这个例外，它把代码撕成了两半。

既然缺的是前驱，那就造一个。在真实头节点前面挂一个不参与比较的哑节点，链表里每个节点就都有前驱了，删头和删中间彻底同构。

剩下的关键是游标何时前进。用 cur 指向「已确认保留的最后一个节点」，每次只检查 cur.next：如果它要删，就执行 cur.next = cur.next.next，此时 cur 必须原地不动，因为新接上来的后继还没被检查过；如果它要留，才把 cur 前移一格。

不变量是：每轮循环开始时，从 dummy 到 cur 这一段中已经不含任何值为 val 的节点，且 cur.next 是下一个待判定的节点。 循环在 cur.next 为空时结束，此时不变量覆盖了整条链，说明删除已经彻底。返回 dummy.next 即为新头：原头被删时它自动指向后面第一个保留节点，全删光时它就是空。

解题步骤

新建 dummy 并令 dummy.next = head。这一步是全部简化的来源，它把「删头节点」变成了「删 dummy 的后继」。

令 cur = dummy。从哑节点起步而不是从 head 起步，才能让第一个被检查的对象是 head 本身。

循环条件是 cur.next != null，即还有待判定的节点。判断的是后继而非 cur 自己，与「盯住后继」的整体设计一致。

若 cur.next.val == val，执行 cur.next = cur.next.next 摘除节点，并且不移动 cur。这是本题与「只删一个」类题目的核心差别：连续待删节点必须靠原地重复检查才能一次性删净。

否则把 cur 前移一格，表示这个节点确认保留。

循环结束后返回 dummy.next。不能返回 head，因为 head 可能早已被摘除，只是一个游离对象。

以 head = [1,2,6,3,4,5,6]、val = 6 走一遍：挂上哑节点后链是 dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6，cur = dummy。第一轮，cur.next 是 1，值不等，cur 前移到节点 1。第二轮，cur.next 是 2，保留，cur 前移到节点 2。第三轮，cur.next 是 6，命中，执行摘除后节点 2 的 next 变成 3，cur 仍停在节点 2。第四轮，cur.next 现在是 3，保留，cur 前移到 3。第五、六轮同理保留 4 和 5，cur 依次前移到 4、5。第七轮，cur.next 是尾部的 6，命中，执行 cur.next = cur.next.next，而那个 6 的后继为空，于是节点 5 的 next 被置空，cur 仍停在 5。第八轮，cur.next 为空，循环退出。返回 dummy.next 即节点 1，链为 [1,2,3,4,5]。再以 head = [7,7,7,7]、val = 7 走一遍：cur 始终停在 dummy，四轮里每轮都命中并摘除一个，dummy.next 依次变为第二、第三、第四个 7，最后变为空，循环退出，返回空链表。

代码实现

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;

        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

func removeElements(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Next: head}
    cur := dummy
    for cur.Next != nil {
        if cur.Next.Val == val {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return dummy.Next
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是链表长度。每个节点恰好被作为 cur.next 检查一次，检查后要么被摘除、要么被跨过，两种结果都让待判定集合减少一个，所以总轮数就是 $n$。

空间复杂度：$O(1)$，只额外创建一个哑节点和一个游标指针，不随链表长度增长。

关键点总结

哑节点是链表题消除头部特例的标准动作。判断要不要加，只需问一句「头节点会不会被改动」，会就加，代价只有一个对象。

删除类遍历中，游标推进必须是有条件的：删除时原地不动，保留时才前进。把「推进」和「保留」绑定在一起，是防止漏删连续目标的关键。

循环条件盯 cur.next 而不是 cur，这样每轮的判定对象和可修改对象天然对齐，不需要额外维护前驱变量。

返回值要写 dummy.next 而非 head，因为 head 表示的是「原来的头」，删除后未必还是「现在的头」。

面试视角：先说「先剥头部再处理中间」的两段式写法并指出其重复与易漏，再引入哑节点合并成一段，能完整展示化简过程。若面试官要求递归版本，可以给出 head.next = removeElements(head.next, val); return head.val == val ? head.next : head;，同时主动说明它的栈空间是 $O(n)$。

面试视角：常见追问是「和只删第一个匹配节点有什么区别」。答案落在游标推进上：只删一个时找到就退出，删全部时删完必须原地重查，这一句话能体现你真的理解循环结构而不是背模板。

易错点总结

错误写法：删除后仍然执行 cur = cur.next。用例 head = [1,2,6,6,3]、val = 6 → 摘掉第一个 6 后游标前移，第二个 6 被跳过，结果是 [1,2,6,3]，连续目标漏删。

错误写法：cur 从 head 起步而不是从 dummy 起步。用例 head = [6,1,2]、val = 6 → 头节点从未被检查，返回 [6,1,2]，删除完全失效。

错误写法：返回 head 而不是 dummy.next。用例 head = [7,7,7,7]、val = 7 → head 指向已被摘除的第一个 7，返回结果仍是 [7,7,7,7] 或以孤立节点开头的错误链。

错误写法：循环条件写成 cur != null 并在体内访问 cur.next.val。用例 head = [1,2]、val = 3 → 游标走到尾节点后 cur.next 为空，读它的 val 直接抛空指针异常。

错误写法：删除时写成 cur = cur.next.next，把指针移动误当成指针改写。用例 head = [1,6,2]、val = 6 → 链表结构没有任何变化，只是游标跳过了目标，返回原链。

错误写法：不加哑节点，只在开头写一次 if (head.val == val) head = head.next;。用例 head = [6,6,1]、val = 6 → 只剥掉一个头节点，第二个 6 变成新头并留了下来，且 head 为空时还会先崩在 head.val 上。

错误写法：用两个变量 pre 和 cur 遍历，但删除后忘记把 cur 更新为 pre.next。用例 head = [1,6,6,2]、val = 6 → cur 指向已被摘除的节点，沿着它的 next 继续走会绕回被删链段，行为不可预期。

错误写法：先统计待删数量再新建一条链复制保留节点，却用值相等判断跳过。用例 head = [1,2,6,3,4,5,6]、val = 6 → 结果虽对，但额外开了 $O(n)$ 空间并新建了节点，不符合原地删除的意图，面试中会被追问。

错误写法：认为链表被删空是非法情形，于是在返回前加 if (dummy.next == null) return head;。用例 head = [7,7,7,7]、val = 7 → 正确答案就是空链表，这条兜底反而把已删除的内容又还了回去。

相似题目

题目	难度	考察点
剑指 Offer 18. 删除链表的节点	简单	只删第一个匹配节点，找到即可结束遍历
83. 删除排序链表中的重复元素	简单	利用有序性比较相邻节点，重复值需保留一个
82. 删除排序链表中的重复元素 II	中等	重复值一个不留，需要先探测整段再统一跳过
面试题 02.01. 移除重复节点	简单	链表无序，需借助哈希集合记录已出现过的值
237. 删除链表中的节点	中等	拿不到前驱，改用复制后继值再删后继的技巧
面试题 02.03. 删除中间节点	简单	同为无前驱删除，考察对值覆盖思路的迁移