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

约 4 分钟
文章信息 3 个分类 2 个标签
分类
LeetCode 中等 LeetCode 75
标签
双指针 链表

题目描述

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

image-20260928234436247

image-20260928234436248

题意分析

删除非空单链表中下标为 floor(n / 2) 的节点，下标从零开始。奇数长度时删除唯一中点，偶数长度时删除两个中点中靠后的那个。

返回删除后的链表头，其他节点的顺序保持不变。只有一个节点时，中点就是头节点，结果为空。删除单链表节点需要调整它前一个节点的连接，因此应定位中点前驱，而不只是中点本身。

解法：快慢指针定位待删节点的前驱

核心思路

[!blue]

快指针每轮走两步，慢指针每轮走一步，可以在快指针到达末尾时找到中间位置。为了得到待删节点的前驱，让快指针从头节点开始，而慢指针从指向头节点的哨兵 dummy 开始，慢指针的起点比真实头节点早一格。

将哨兵视为下标负一。完成 k 轮之后，快指针从头前进了 2k 步，越过尾部时为空；慢指针位于下标 k - 1。当快指针及其后继不再同时存在时，循环总共执行 floor(n / 2) 轮，因此慢指针位于 floor(n / 2) - 1，它的后继正是待删除的中点。

执行 slow.next = slow.next.next，让前驱直接连接被删节点的后继即可。输入非空，目标中点一定存在。单节点时循环不执行，慢指针仍为哨兵，同一条接线操作会把哨兵后继改为空。

删除可能影响头节点，因此最终返回 dummy.next，让普通删除和删头都使用统一结果入口。

解题步骤

  1. 创建指向原头节点的哨兵，令 slow = dummy、fast = head。
  2. 快指针及其后继都存在时，慢指针前进一步，快指针前进两步。
  3. 循环结束后，跳过 slow.next，让它的前驱直接连到后继。
  4. 返回 dummy.next，它包含头节点可能被删除后的新入口。

代码实现

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)$，快慢指针单向移动，删除只调整一次指针。
  • 空间复杂度：$O(1)$，只增加一个哨兵和固定数量的指针。

关键点总结

[!green]

  • 待删下标是向下取整的半长，偶数时对应后一个中点。
  • 慢指针从哨兵开始，终点恰好提前一格，直接得到中点前驱。
  • 哨兵统一处理单节点删头，无需额外复制或重新构造链表。
  • 删除后从哨兵返回入口，不能固定返回旧头指针。

易错点总结

[!yellow]

  • 慢指针也从头开始，却仍删除它的后继，会删到中点之后的位置。
  • 使用偏向前中点的循环规则，与题目偶数时删后中点的要求不符。
  • 未检查快指针和其后继就连续走两步，会访问空指针。
  • 删除完直接返回旧 head，单节点时仍暴露已经应被删除的节点。
  • 只把 slow 变量移动到后继，却没有修改前驱的 next，并不会真正从链表中删除节点。

相似题目

题目 难度 关联与区别
876. 链表的中间结点 简单 同样用快慢指针找到靠后的中间位置，本题让slow提前一格以获得前驱。
19. 删除链表的倒数第 N 个结点 中等 同样先定位待删节点前驱，再用哑节点统一删除头节点的情况。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/16609737
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！