[2095] 删除链表的中间节点
题目描述
给你一个链表的头节点 head。删除链表的中间节点，并返回修改后的链表的头节点 head。
链表的中间节点定义为：如果链表的长度为 n，则中间节点的下标为 ⌊n / 2⌋（从 0 开始）。
示例 1
输入：head = [1,3,4,7,1,2,6]
输出：[1,3,4,1,2,6]
解释：上图表示给出的链表。节点的下标分别标注在每个节点的下方。节点下标 3 是一个中间节点，值为 7。删除该节点后，链表变为 1 -> 3 -> 4 -> 1 -> 2 -> 6。
示例 2
输入：head = [1,2,3,4]
输出：[1,2,4]
解释：上图表示给出的链表。节点下标 2 是一个中间节点，值为 3。删除该节点后，链表变为 1 -> 2 -> 4。
示例 3
输入：head = [2,1]
输出：[2]
解释：上图表示给出的链表。节点下标 1 是一个中间节点，值为 1。删除该节点后，链表变为 2。
解题思路
核心方法：快慢指针（Floyd 判圈法变体）
本题要求删除链表的中间节点，关键在于如何高效地找到中间节点的前驱节点，以便进行删除操作。
步骤详解
边界处理：
- 如果链表为空（head is None）或只有一个节点（head.next is None），删除后链表为空，直接返回 None。
快慢指针定位：
- 初始化 slow 指针指向 head，fast 指针指向 head.next.next。
- 每次循环中，slow 向前移动一步，fast 向前移动两步。
- 当 fast 为 None 或 fast.next 为 None 时，slow 恰好停在中间节点的前一个节点。
删除操作：
- 通过 slow.next = slow.next.next 跳过中间节点，完成删除。
返回结果：
- 返回原链表的头节点 head。
为什么这样定位？
- 当 fast 到达链表末尾时，slow 正好在中间位置的前一个节点。
- 这种初始化方式（fast 从 head.next.next 开始）确保了 slow 始终指向中间节点的前驱，方便直接删除。
复杂度分析
- 时间复杂度：O(n)，只需遍历链表一次，其中 n 为链表长度。
- 空间复杂度：O(1)，只使用了常数个指针变量，没有额外空间开销。
完整代码
# 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]:
# 边界情况：空链表或只有一个节点
if not head or not head.next:
return None
# 快慢指针初始化
slow = head
fast = head.next.next
# 快指针每次走两步，慢指针每次走一步
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 删除中间节点
slow.next = slow.next.next
return head
总结
本题利用快慢指针的技巧，巧妙地找到了中间节点的前驱位置，从而实现了 O(n) 时间复杂度和 O(1) 空间复杂度的高效删除。快慢指针是链表问题中的经典技巧，值得熟练掌握。
