题目
给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。
一、代码实现
func deleteMiddle(head *ListNode) *ListNode {if head == nil || head.Next == nil {return nil}var pre *ListNodeslow, fast := head, headfor fast != nil && fast.Next != nil {fast = fast.Next.Nextpre = slowslow = slow.Next}pre.Next = slow.Nextreturn head
}
二、算法分析
1. 核心思路
- 快慢指针法：通过快指针（一次两步）和慢指针（一次一步）同步遍历链表，当快指针到达末尾时，慢指针正好指向中间节点的前驱
- 前驱维护：通过
pre指针记录慢指针的前驱节点，便于直接修改指针完成删除操作
2. 关键步骤
- 边界处理：若链表为空或仅有一个节点，直接返回
nil - 指针初始化：
pre初始化为nil，slow和fast初始化为头节点 - 同步遍历：快指针每次走两步，慢指针每次走一步，同时更新
pre为慢指针前驱 - 删除操作：当快指针无法继续移动时，通过
pre.Next = slow.Next跳过中间节点
3. 复杂度
| 指标 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 单次遍历链表 |
| 空间复杂度 | O(1) | 仅需固定数量的指针变量 |
三、图解示例
四、边界条件与扩展
1. 特殊场景验证
- 单节点链表：输入
[5]→ 返回nil - 双节点链表：输入
[1,2]→ 变为[1] - 偶数长度链表：输入
[1,2,3,4]→ 中间节点3被删除，变为[1,2,4]
2. 多语言实现
# Python实现（快慢指针）
class Solution:def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head or not head.next:return Nonepre, slow, fast = None, head, headwhile fast and fast.next:fast = fast.next.nextpre = slowslow = slow.nextpre.next = slow.nextreturn head
// Java实现（指针同步移动）
class Solution {public ListNode deleteMiddle(ListNode head) {if (head == null || head.next == null) return null;ListNode pre = null, slow = head, fast = head;while (fast != null && fast.next != null) {fast = fast.next.next;pre = slow;slow = slow.next;}pre.next = slow.next;return head;}
}
五、总结与扩展
1. 核心创新点
- 单次遍历优化：相比两次遍历法（先计算长度再删除），快慢指针法将时间复杂度优化至严格O(n)
- 前驱动态维护：通过
pre指针的同步更新，避免删除时二次遍历查找前驱节点
2. 扩展应用
- 链表环检测：快慢指针可扩展用于检测链表是否存在环
- 倒数第K节点：调整快慢指针步差可快速定位特定位置节点
- 多级链表操作：该模式可推广至需要定位特定位置节点的场景（如分块处理）
3. 工程优化方向
- 内存安全：显式释放被删除节点的内存（如C/C++）
- 并发控制：添加锁机制支持多线程环境下的链表操作
