LeetCode 2095. 删除链表的中间节点

2026-07-14 HGNULB 约 9 分钟

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

分类

题目描述

✅ 2095. 删除链表的中间节点

题意分析

给一条单链表，删掉「中间节点」后返回新的头节点。这里的「中间」不是凭感觉的中间，而是一个精确定义：设链表长度为 n，要删的是下标 ⌊n/2⌋ 的节点，下标从 0 起算。

这个定义必须先算清楚，否则偶数长度一定翻车。n 为奇数时 ⌊n/2⌋ 就是唯一的正中间；n 为偶数时有两个居中的节点，⌊n/2⌋ 取的是偏右那个 —— 例如 n=4 删下标 2 而不是下标 1，官方样例 [1,2,3,4] → [1,2,4] 删掉的正是值为 3 的节点。把前几项列出来核对最稳妥：n=1 删 0，n=2 删 1，n=3 删 1，n=4 删 2，n=5 删 2，n=6 删 3，n=7 删 3。

第二个要点是结构性的：单链表只能往后走，要摘掉某个节点，手里必须先攥着它的前驱，把前驱的 next 越过它接到后继上。所以真正需要定位的目标不是下标 ⌊n/2⌋，而是下标 ⌊n/2⌋ - 1。而当 ⌊n/2⌋ 恰好为 0（也就是 n=1）时，这个前驱根本不存在于链表之中，这就是所有特判的来源。

边界只有一个，但必须记牢：n=1 时删掉唯一的节点，链表变空，必须返回空，而不是把原来那个节点交回去。约束里写着节点数在 1 到 $10^5$ 之间，前者说明不用操心空输入，后者则在暗示别写反复遍历的解法，最好一趟走完并且只用常数额外空间。

解法：快慢指针定位中间节点的前驱

核心思路

长度未知却要定位到 ⌊n/2⌋，最直觉的做法是先遍历一趟数出 n、再遍历半趟走过去。但只要让两个指针以固定的速度差同时出发，就能把这两趟压成一趟：fast 每轮走两步，slow 每轮走一步，全程维持不变量 —— fast 走了 2k 步时 slow 恰好走了 k 步。当 fast 因为走不出第二步而停下时，它走过的路程已经覆盖了整条链表，此时 slow 走过的步数正好是总长的一半，这就是「一趟定位分数位置」。

真正的关键在于让 slow 落在前驱上，而不是中点本身。假如 slow 停在下标 ⌊n/2⌋，手里只有中点，那么 slow.next = slow.next.next 删掉的是中点的后继，方向整个错了；而单链表没有回头路，想补救就得再遍历一趟去找前驱，一趟的优势白白丢掉。所以要在起点上做手脚：把 slow 的出发位置整体往前挪一格，它抵达的位置自然也往前一格，正好落在 ⌊n/2⌋ - 1。

「往前挪一格」在 n=1 时会挪到链表外面去，于是哨兵节点登场：造一个 dummy 让 dummy.next 指向 head，slow 从 dummy 出发、fast 仍从 head 出发。这样无论 ⌊n/2⌋ 是不是 0，slow 手里永远有一个合法的前驱可用 —— n=1 时 slow 一步都不走、原地停在 dummy 上，dummy.next = dummy.next.next 就把唯一的节点摘掉了，最后 return dummy.next 自然返回空。「删除头节点」这个特判被哨兵整个吃掉了，正文里一个 if 都不用写，这也是面试官在链表删除题上最想看到的处理方式。

循环条件必须是 fast != null && fast.next != null：前半句管住 fast 已经走到空的情况，后半句保证 fast.next.next 不会踩空，两句缺一不可。顺带一提，「先数长度再走一半」其实是同一个思路的两趟版本，走 ⌊n/2⌋ 步同样要从哨兵起步才能停在前驱上；正确性一致，只是多扫一遍链表。

解题步骤

建哨兵 dummy 并令 dummy.next = head。为什么：给 slow 一个位于链表之外的合法起点，从根上消除 ⌊n/2⌋ = 0 时没有前驱的特判。

令 slow = dummy、fast = head。为什么：两者起点相差一格，fast 到头时 slow 才会落在 ⌊n/2⌋ - 1 而不是 ⌊n/2⌋。

当 fast != null && fast.next != null 时进入循环。为什么：fast 每轮要迈两步，两个判空分别防住「已经越过尾部」和「只剩一个节点、迈不出第二步」。

循环体内 slow 走一步、fast 走两步。为什么：维持 fast 步数是 slow 两倍的不变量，fast 走完全长时 slow 刚好走完半程。

循环结束后执行 slow.next = slow.next.next。为什么：slow 此时是待删节点的前驱，把它的 next 越过待删节点直接接到后继，删除就完成了。

返回 dummy.next。为什么：头节点有可能已经被摘掉，head 是失效的旧引用，只有 dummy.next 才是真正的新头。

以 [1,2,3,4] 走一遍：n=4，应删下标 2（值 3）。初始 slow = dummy、fast = 节点1。第一轮，fast 的 next 是节点2 不为空，于是 slow 前进到节点1（下标 0），fast 前进两步到节点3（下标 2）。第二轮，fast = 节点3 的 next 是节点4 不为空，于是 slow 前进到节点2（下标 1），fast 越过节点4 变成空。第三轮判空失败，退出循环，slow 停在下标 1，正是 ⌊4/2⌋ - 1。执行 slow.next = slow.next.next，节点2 直接指向节点4，节点3 被摘出链表，return dummy.next 得到 [1,2,4]。

n=1 边界：输入 [7]，slow = dummy、fast = 节点7，因为 fast.next 为空，循环一轮都不进，slow 原地停在 dummy 上。执行 dummy.next = dummy.next.next，即 dummy.next 变成空，返回 dummy.next 得到空链表，符合「删掉唯一节点后链表为空」。

n=2 边界：输入 [2,1]，应删下标 1。第一轮 fast = 节点2 的 next 不为空，slow 前进到节点2（下标 0），fast 越过节点1 变成空，随即退出。slow 停在下标 0，删掉 slow.next（下标 1、值为 1 的节点），返回 [2] —— 偶数长度删偏右那个，与定义吻合。

代码实现

class Solution {
    public ListNode deleteMiddle(ListNode head) {
        // 哨兵让 slow 有一个链表外的起点，从根上消除「删头节点」的特判。
        ListNode dummy = new ListNode(0, head);
        // slow 起点比 fast 早一格，因此终点也早一格，落在待删节点的前驱上。
        ListNode slow = dummy;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            // 不变量：fast 走 2k 步时 slow 走 k 步。
            slow = slow.next;
            fast = fast.next.next;
        }
        // slow 是下标 ⌊n/2⌋ 节点的前驱，直接跨过待删节点。
        slow.next = slow.next.next;
        // 头节点可能已被删除，必须返回 dummy.next 而不是 head。
        return dummy.next;
    }
}

func deleteMiddle(head *ListNode) *ListNode {
    // 哨兵让 slow 有一个链表外的起点，从根上消除「删头节点」的特判。
    dummy := &ListNode{Next: head}
    // slow 起点比 fast 早一格，因此终点也早一格，落在待删节点的前驱上。
    slow, fast := dummy, head
    for fast != nil && fast.Next != nil {
        // 不变量：fast 走 2k 步时 slow 走 k 步。
        slow = slow.Next
        fast = fast.Next.Next
    }
    // slow 是下标 ⌊n/2⌋ 节点的前驱，直接跨过待删节点。
    slow.Next = slow.Next.Next
    // 头节点可能已被删除，必须返回 dummy.Next 而不是 head。
    return dummy.Next
}

复杂度分析

时间复杂度：$O(n)$，fast 至多走满整条链表一趟就停下，slow 走的是半趟，两者共用同一次遍历，没有任何回头或重扫。

空间复杂度：$O(1)$，只额外用了一个哨兵节点和两个指针，与链表长度无关；全程原地改指针，没有建新链表或辅助容器。

关键点总结

要删节点，就让指针停在它的前驱上。单链表的删除动作只能由前驱发起，定位目标要顺着这个约束往前移一格，而不是先定位到目标再想办法找前驱。

哨兵节点专治头节点特判。凡是「可能删掉头节点」的链表题，加一个 dummy 就能把头和其他节点抹平成同一种情况，收尾统一 return dummy.next；代价是一个节点的空间，换来的是少写一个容易漏的 if。

通过错开起点来平移终点。快慢指针的落点由「速度差 + 起点差」共同决定，想让慢指针停在前驱，改起点比改循环条件安全得多 —— 起点差一格就是终点差一格，推导直观且不容易写错边界。

走两步的指针必须做两次判空。fast != null 和 fast.next != null 各自拦住一种越界，写成一个条件就会在某类长度上炸掉。

面试视角：这题面试官几乎一定会追问两件事 —— 一是「奇偶长度下你的两个指针分别停在哪」，请当场用 n=1,2,3,4 把慢指针的下标报出来（依次是 dummy、0、0、1，即 ⌊n/2⌋ - 1），说明偶数取的是偏右的中点；二是「能不能一趟完成」，先数长度再走一半是两趟，快慢指针把它压成一趟，同时强调哨兵让「删头」不再需要特判。能主动讲出不变量和 n=1 返回空这两点，基本就过了。

易错点总结

慢指针从 head 出发，最终停在中点本身：[2,1] → slow 停在下标 1，slow.next 已经是空，slow.next.next 直接抛空指针异常；[1,2,3] → 输出 [1,2]，删掉的是中点的后继而非中点。这是本题最常见的错法，根因就是没意识到删除必须由前驱发起。

提前 if (head.next == null) return head; 想省掉单节点情况：[1] → 输出 [1]，而正确答案是空链表；其余长度全部正常，n=1 是唯一暴露口，本地随手测两三个用例极易漏掉。

删完返回 head 而不是 dummy.next：[1] → 输出 [1]，因为 head 恰好就是被摘掉的那个节点，head 已成失效引用。这条最阴 —— n≥2 时全对，三个官方样例也全过，只有 n=1 会挂。

循环条件写成 fast.next != null && fast.next.next != null：[1,2,3,4] → 输出 [1,3,4]（删了下标 1），[2,1] → 输出 [1]（删了下标 0）。偶数长度慢指针少走一步，删成了 ⌊n/2⌋ - 1 偏左那个；奇数长度反而正确，官方样例 1 长度为 7 会侥幸通过，掩盖住 bug。

fast 从 head.next 出发，以为能「提前一步」：与上一条同病同果，[1,2,3,4] → [1,3,4]，[2,1] → [1]，偶数长度一律偏左一位。起点想动就得重新推一遍落点，不能凭感觉。

循环条件只写 while (fast != null)，忘了检查 fast.next：[1,2,3]、[1,2,3,4,5] 一律抛空指针异常，因为奇数长度下 fast 会停在最后一个节点，fast.next.next 就踩空了；偶数长度侥幸不崩，错觉是「代码没问题」。

循环条件放成 while (fast != null) 再在循环体里用三目补空：[1,2,3] → 输出 [1,2]（删下标 2），[1,3,4,7,1,2,6] → 输出 [1,3,4,7,2,6]（删了下标 4 的 1 而不是下标 3 的 7）。补了空判不崩了，但慢指针多走一步，奇数长度整体偏右一位。

fast 和 slow 都从哨兵出发：[1,2,3] → 输出 [1,2]（删下标 2），[1] → 输出 [1]（slow.next 为空，加判空后什么都没删）。哨兵只该给 slow 用，fast 跟着挪就把一格的起点差抹平了。

先数长度但多走了一步，写成走 n/2 + 1 步：[1,2,3,4] → 输出 [1,2,3]，[2,1] → 输出 [2,1]（原样返回）。从哨兵起步只该走 ⌊n/2⌋ 步就停在前驱，多一步就落到中点本身了。

相似题目

题目	难度	考察点
876. 链表的中间结点	简单	同样快慢指针求中点，但只要返回中点本身，慢指针从 `head` 起步，无需前驱和哨兵
19. 删除链表的倒数第 N 个结点	中等	双指针间距固定为 `n` 步而非二倍速，定位的是倒数位置而不是分数位置，同样靠哨兵消除删头特判
237. 删除链表中的节点	中等	只给待删节点、拿不到前驱，只能复制后继的值再摘掉后继，反向印证本题为何必须停在前驱
203. 移除链表元素	简单	按值批量删除而非按下标删一个，前驱指针只在不删时才前移，哨兵的作用完全一致
143. 重排链表	中等	快慢指针求中点只是第一步，后面还要反转后半段并交叉拼接，中点是中间产物不是答案