LeetCode算法题(Go语言实现)_29

题目

给你一个链表的头节点 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 *ListNode
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        pre = slow
        slow = slow.Next
    }
    pre.Next = slow.Next
    return head
}

二、算法分析

1. 核心思路

• 快慢指针法：通过快指针（一次两步）和慢指针（一次一步）同步遍历链表，当快指针到达末尾时，慢指针正好指向中间节点的前驱
• 前驱维护：通过pre指针记录慢指针的前驱节点，便于直接修改指针完成删除操作

2. 关键步骤

1. 边界处理：若链表为空或仅有一个节点，直接返回nil
2. 指针初始化：pre初始化为nil，slow和fast初始化为头节点
3. 同步遍历：快指针每次走两步，慢指针每次走一步，同时更新pre为慢指针前驱
4. 删除操作：当快指针无法继续移动时，通过pre.Next = slow.Next跳过中间节点

3. 复杂度

三、图解示例

四、边界条件与扩展

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 None
        pre, slow, fast = None, head, head
        while fast and fast.next:
            fast = fast.next.next
            pre = slow
            slow = slow.next
        pre.next = slow.next
        return 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++）
• 并发控制：添加锁机制支持多线程环境下的链表操作