LeetCode 每日一题笔记

0. 前言

• 日期：2026.06.15
• 题目：2095. 删除链表的中间节点
• 难度：中等
• 标签：链表、双指针、快慢指针

1. 题目理解

问题描述： 给定链表头结点 head，链表长度为 n，中间节点下标为 $\lfloor n/2\rfloor$，删除该中间节点并返回修改后的链表头。

示例：

输入：head = [1,3,4,7,1,2,6] 输出：[1,3,4,1,2,6] 解释：链表长度7，中间下标3，删除值为7的节点。

2. 解题思路

核心观察

• 快慢指针：fast一次走两步，slow一次走一步，fast到达末尾时slow正好指向中间节点。
• 需要一个前驱指针 pre 跟随slow，用于跳过中间节点完成删除操作。
• 边界：链表仅有一个节点时直接返回null。

算法步骤

1. 特判单节点链表，直接返回null；
2. 初始化slow、fast指向头，pre记录slow前驱；
3. 循环移动快慢指针，同步更新pre；
4. 将pre的next指向slow.next，跳过中间节点完成删除；
5. 返回原头结点。

3. 代码实现

package lc2095;

class Solution {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode deleteMiddle(ListNode head) {
        if (head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        ListNode last = head;
        boolean flag = false;
        while (fast.next != null && fast.next.next != null) {
            last = slow;
            slow = slow.next;
            fast = fast.next.next;
            if (fast.next == null) {
                flag = true;
            }
        }
        if (flag) {
            last.next = slow.next;
        } else {
            if (slow.next != null) {
                slow.next = slow.next.next;
            } else {
                slow.next = null;
            }
        }
        return head;
    }
}

4. 代码优化说明

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
  */
class Solution {
public ListNode deleteMiddle(ListNode head) {
    // 仅有一个节点，直接返回空
    if (head.next == null) {
        return null;
    }
    ListNode slow = head;
    ListNode fast = head;
    // pre保存慢指针的前一个节点，用于删除中间节点
    ListNode pre = null;
    // 快指针每次两步，慢指针一步，循环至fast到达链表尾部
    while (fast != null && fast.next != null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    // 跳过中间节点slow，完成删除
    pre.next = slow.next;
    return head;
}
}

5. 复杂度分析

• 原始实现 时间：$O(n)$，单次遍历链表 空间：$O(1)$，常数临时变量；多余flag与分支判断，逻辑冗余
• 优化快慢指针版 时间：$O(n)$，仅一次链表遍历 空间：$O(1)$，仅三个指针变量；消除多余布尔标记与多层if分支，逻辑极简

6. 总结

• 核心技巧：快慢指针定位链表中点，前驱指针完成节点删除。
• 优化亮点：去除冗余标记变量、合并多分支删除逻辑，代码可读性与执行效率提升。
• 边界要点：单独处理长度为1的链表，避免空指针异常。