LeetCode 剑指 Offer 18. 删除链表的节点

2020-08-29 HGNULB 约 7 分钟

文章信息 11 个分类 1 个标签

分类

LeetCode CodeTop 简单已解决已掌握 2-5 字节跳动快手猿辅导剑指 Offer 剑指 Offer（第 2 版）

题目描述

✅ 剑指 Offer 18. 删除链表的节点

题意分析

给一条单链表的头节点和一个整数 val，要求把链表里值等于 val 的那个节点删掉，并返回删除后的链表头。

有几个信号决定了写法。第一，题目保证链表中值互不相同且 val 一定存在，所以只需要删一个节点，找到就结束，不必扫完全链；不过写代码时留一层「找不到就原样返回」的保护，成本为零而鲁棒性更好。第二，返回值是链表头而不是 void，这暗示头节点本身可能就是要删的那个，返回值不能想当然地写成 head。

从操作层面看，单链表删除一个节点只能通过它的前驱来完成——把前驱的 next 越过它。所以真正要找的不是目标节点，而是目标节点的前驱。

边界要单独想清楚三种：目标就是头节点（没有真正的前驱）、目标是尾节点（越过后前驱的 next 变成空）、以及链表只有一个节点且正好要删（结果是空链表）。

解法：哑节点统一删除位置

核心思路

最朴素的写法是分两种情况：先判断 head.val == val，是就返回 head.next；否则再用 pre 从 head 开始往后找。这能过，但代码里出现了两段结构相似、只差一点的逻辑，白板上很容易在其中一支里写错返回值或漏掉判空。瓶颈在于「头节点没有前驱」这个例外，它逼着我们额外开一条分支。

观察这个例外的本质：不是删除逻辑不同，而是头节点缺一个前驱。既然缺什么就补什么，那就凭空造一个节点接在头节点前面，让它充当头节点的前驱。这个节点不参与任何值比较，只提供一个可写的 next 字段。

加上这个哑节点后，链表里每个真实节点都有前驱了，删除操作彻底统一成一句 pre.next = pre.next.next。

不变量是：循环的每一时刻，pre 都指向「尚未被检查过的那段链」的前一个位置，即 pre.next 才是当前待判定的节点；且从 dummy 到 pre 这一段中不存在值为 val 的节点。循环结束时要么 pre.next 为空（全链扫完没找到），要么 pre.next 正是待删节点，两种情况都能用一个判空区分开。返回时统一取 dummy.next，因为它总是当前真实头节点，无论原头节点是否被删。

解题步骤

新建 dummy 并令 dummy.next = head。这一步是整个解法的支点：它把「删头节点」变成了「删 dummy 的后继」，与删中间节点完全同构。

令 pre = dummy 开始遍历。从 dummy 而不是 head 起步，才能让第一个被检查的节点是 head 本身，否则头节点会被跳过。

循环条件写成 pre.next != null && pre.next.val != val。两个条件的顺序不能颠倒：必须先确认 pre.next 非空，才有资格读它的 val，靠的是逻辑与的短路求值。

循环退出后判断 pre.next != null。非空说明找到了目标，执行 pre.next = pre.next.next 把它从链上摘除；为空说明整条链都没有目标值，什么都不做。

返回 dummy.next。不能返回 head，因为原头节点可能已经被摘掉，那时 head 指向的是一个已经脱离链表的孤立节点。

以 head = [4,5,1,9]、val = 5 走一遍：先建 dummy，此时链是 dummy → 4 → 5 → 1 → 9，pre 指向 dummy。第一轮判断：pre.next 是 4，非空且 4 != 5，pre 前进到节点 4。第二轮判断：pre.next 是 5，非空但 5 == 5，条件不成立，循环退出，此时 pre 停在节点 4。退出后 pre.next 是节点 5，非空，执行 pre.next = pre.next.next，即把节点 4 的 next 从 5 改成 1。链变成 dummy → 4 → 1 → 9，节点 5 已不可达。返回 dummy.next 也就是节点 4，输出 [4,1,9]。再换 head = [4,5,1,9]、val = 4 走一遍：pre 起始在 dummy，第一轮判断 pre.next 是 4 且 4 == 4，循环一次都没进就退出，pre 仍是 dummy；随后 dummy.next = dummy.next.next，链变成 dummy → 5 → 1 → 9，返回 dummy.next 即节点 5，头节点被正确替换。

代码实现

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

        // pre 永远指向待检查节点的前驱，删除头节点和中间节点逻辑一致。
        while (pre.next != null && pre.next.val != val) {
            pre = pre.next;
        }

        if (pre.next != null) {
            pre.next = pre.next.next;
        }

        return dummy.next;
    }
}

func deleteNode(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Next: head}
    pre := dummy

    // pre 永远指向待检查节点的前驱，删除头节点和中间节点逻辑一致。
    for pre.Next != nil && pre.Next.Val != val {
        pre = pre.Next
    }

    if pre.Next != nil {
        pre.Next = pre.Next.Next
    }

    return dummy.Next
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是链表长度。最坏情况下目标位于尾部或根本不存在，需要把每个节点检查一次；每次检查只做一次比较和一次指针移动。

空间复杂度：$O(1)$，只额外创建了一个哑节点和一个指针变量，与链表长度无关。

关键点总结

哑节点是链表题的通用消歧手段：凡是「头节点可能被改动」的题（删除、插入、区间反转、分组处理），先加哑节点几乎不会错，代价只有一个对象。

单链表的删除必须通过前驱完成，所以遍历时该盯住的是 pre.next 而不是 cur。把循环写成「检查后继」而非「检查自己」，删除时就不用再回头找前驱。

判空与取值的先后顺序依赖短路求值。写 pre.next != null && pre.next.val != val 是刻意的，两个条件互换就会在链尾解引用空指针。

返回值要看语义而不是看变量名。这里必须返回 dummy.next 而非 head，因为 head 只是「原来的头」，未必是「现在的头」。

面试视角：先说分头节点和非头节点两种情况的朴素写法，再指出它的重复逻辑，然后引入哑节点消掉分支，比一上来就写哑节点更能体现思考过程。

面试视角：常见追问是「如果要删除所有等于 val 的节点怎么改」。答案是把 if 换成循环、并在未删除时才移动 pre，可以顺势提到这正是第 203 题。

易错点总结

错误写法：pre 从 head 起步而不是从 dummy 起步。用例 head = [4,5,1,9]、val = 4 → 头节点根本没被检查过，返回的仍是 [4,5,1,9]，删除完全失效。

错误写法：循环条件写成 pre.next.val != val && pre.next != null。用例 head = [4,5,1,9]、val = 7 → 走到尾节点后 pre.next 为空，先读 val 直接抛空指针异常。

错误写法：最后返回 head 而不是 dummy.next。用例 head = [4,5,1,9]、val = 4 → 返回的是已经被摘除的孤立节点 4，输出变成 [4,5,1,9] 或只有 [4]，取决于摘除时是否清空了它的 next。

错误写法：删除时写成 pre = pre.next.next，把指针移动误当成指针改写。用例 head = [4,5,1,9]、val = 5 → 链表结构一个字节都没变，只是 pre 挪了位置，返回原链。

错误写法：省略删除前的 pre.next != null 判断，无条件执行 pre.next = pre.next.next。用例 head = [4,5,1,9]、val = 7 → 目标不存在时 pre.next 已经是空，解引用直接崩溃。

错误写法：循环里用 cur 遍历并在找到目标后回头找前驱，却没有单独维护 pre。用例 head = [4,5,1,9]、val = 1 → 单链表无法从 cur 反向取前驱，只能重新从头扫，复杂度退化到 $O(n^2)$ 且极易写漏。

错误写法：找到目标后继续循环，试图删掉所有等值节点。用例本题保证值唯一时结果虽然相同，但若换成 head = [1,2,1]、val = 1 → 会删掉两个节点，与「只删第一个」的语义不符。

错误写法：用 head.val == val 做特判后直接返回 head.next，却忘了 head 本身可能为空。用例 head = [] → 读取空链表的 val 立刻抛异常，而哑节点写法天然免疫这一情况。

相似题目

题目	难度	考察点
203. 移除链表元素	简单	删除全部等值节点，删除后 `pre` 不能前进
83. 删除排序链表中的重复元素	简单	利用有序性只比较相邻节点，重复值保留一个
82. 删除排序链表中的重复元素 II	中等	重复值一个不留，需要成段跳过并回退判定
237. 删除链表中的节点	中等	拿不到前驱，改用「复制后继值再删后继」的技巧
19. 删除链表的倒数第 N 个结点	中等	位置由倒数下标给出，用双指针一次遍历定位
面试题 02.01. 移除重复节点	简单	无序链表去重，需要额外的哈希集合记录已出现值
面试题 02.03. 删除中间节点	简单	只给待删节点本身，考察对「值覆盖」思路的迁移