M2095.删除链表的中间节点

https://leetcode.cn/problems/delete-the-middle-node-of-a-linked-list/

给你一个链表的头节点 head 。删除链表的 中间节点 ，并返回修改后的链表的头节点 head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

示例 1：

输入：head = [1,3,4,7,1,2,6]
输出：[1,3,4,1,2,6]
解释：
上图表示给出的链表。节点的下标分别标注在每个节点的下方。
由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。
返回结果为移除节点后的新链表。

示例 2：

输入：head = [1,2,3,4]
输出：[1,2,4]
解释：
上图表示给出的链表。
对于 n = 4 ，值为 3 的节点 2 是中间节点，用红色标注。

示例 3：

输入：head = [2,1]
输出：[2]
解释：
上图表示给出的链表。
对于 n = 2 ，值为 1 的节点 1 是中间节点，用红色标注。
值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。

提示：

链表中节点的数目在范围 [1, 10^5] 内
1 <= Node.val <= 10^5

这道题可以通过快慢指针（双指针）的方法来高效解决。

解题思路

为了删除链表的中间节点，我们需要：

找到中间节点的前驱节点：这样我们才能让前驱节点的 next 指向中间节点的下一个节点，从而达到删除的目的。
处理边界情况：当链表长度为 1 时，删除中间节点后链表变为空（返回 None）。

我们可以利用快慢指针的思想，并引入一个虚拟头节点（Dummy Node）：

设一个虚拟头节点 dummy，让 dummy.next = head。
初始化：slow 指向 dummy，fast 指向 head。
移动规则：fast 每次向后移动两步，slow 每次向后移动一步。
停止条件：当 fast 为空（None）或 fast.next 为空时停止移动。
此时，slow 恰好指向中间节点的前驱节点。我们只需执行 slow.next = slow.next.next 即可将中间节点删除。

代码实现

python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 创建虚拟头节点，以便能够方便地处理头节点的删除以及链表长度为 1 的边界情况
        dummy = ListNode(0, head)
        slow = dummy
        fast = head
        
        # 快指针每次走两步，慢指针每次走一步
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            
        # 此时 slow 指向中间节点的前一个节点，将其指向下下一个节点，即完成了删除
        slow.next = slow.next.next
        
        return dummy.next

模拟执行过程

以示例 2 为例，输入为 head = [1, 2, 3, 4]，长度 $n = 4$ ，需要删除下标为 $⌊ 4 / 2 ⌋ = 2$ 的节点（即值为 3 的节点）：

初始化：
- 链表结构：dummy(0) -> 1 -> 2 -> 3 -> 4 -> None
- slow 指向 dummy(0)，fast 指向 1。
第一轮循环：
- fast 移动两步到达 3。
- slow 移动一步到达 1。
第二轮循环：
- fast 移动两步到达 None。
- slow 移动一步到达 2。
循环结束（因为 fast 已经为 None）：
- slow 目前指向 2。
- 执行 slow.next = slow.next.next，即 2.next = 4。
- 链表变为 dummy(0) -> 1 -> 2 -> 4 -> None。
返回 dummy.next 即为 [1, 2, 4]。

复杂度分析

时间复杂度： $O (n)$ 。快指针每次走两步，最多遍历一次链表。
空间复杂度： $O (1)$ 。只使用了常数个额外指针空间。

M2095.删除链表的中间节点 ​

M2095.删除链表的中间节点