Delete the Middle Node of a Linked List

題目描述

給定一個 Linked List 的 head，刪除中間節點並回傳修改後的 head。中間節點定義為第 ⌊n/2⌋ 個節點（0-indexed）。

輸入: [1,3,4,7,1,2,6]
輸出: [1,3,4,1,2,6]
解釋: 中間節點是 index 3 的 7

輸入: [1,2,3,4]
輸出: [1,2,4]
解釋: 中間節點是 index 2 的 3

解題思路

建立 dummy 節點

建立 dummy 節點指向 head，讓 slow 有一個「提前一步」的起點

初始化快慢指針

slow 從 dummy 開始、fast 從 head 開始，這樣 slow 比 fast 慢一個節點

移動指針

每一步 slow = slow.next（走 1 步）、fast = fast.next.next（走 2 步）

fast 到尾

fast 為 null 或 fast.next 為 null 時停止，此時 slow.next 恰好是中間節點

刪除中間

執行 slow.next = slow.next.next 跳過中間節點完成刪除

程式碼

C#

csharp

public class Solution {
    public ListNode DeleteMiddle(ListNode head) {
        if (head.next == null) return null; // 只有一個節點
 
        // slow 從 dummy 開始，這樣停下時 slow.next 就是中點
        var dummy = new ListNode(0, head);
        var slow = dummy;
        var fast = head;
 
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
 
        slow.next = slow.next.next; // 跳過中間節點
        return dummy.next;
    }
}

TypeScript

typescript

function deleteMiddle(head: ListNode | null): ListNode | null {
    if (!head || !head.next) return null; // 空或只有一個節點
 
    const dummy = new ListNode(0, head);
    let slow: ListNode = dummy;
    let fast: ListNode | null = head;
 
    while (fast && fast.next) {
        slow = slow.next!;
        fast = fast.next.next;
    }
 
    slow.next = slow.next!.next; // 跳過中間節點
    return dummy.next;
}

Python

python

def deleteMiddle(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head.next:
        return None  # 只有一個節點
 
    dummy = ListNode(0, head)
    slow = dummy
    fast = head
 
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
    slow.next = slow.next.next  # 跳過中間節點
    return dummy.next

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |

Time 為 O(n) 是因為 fast 指針遍歷整個鏈表一次，走了 n/2 步（每步跳 2 個節點）。Space 為 O(1) 是因為只用了 dummy、slow、fast 三個指針變數，不隨輸入規模增長。

邊界情況

只有一個節點：[1] 中間就是自己，刪除後回傳 null，需要特判 head.next == null
只有兩個節點：[1,2] 中間是 index 1 的節點 2，刪除後回傳 [1]
奇數 vs 偶數長度：奇數長度中間唯一確定；偶數長度取 ⌊n/2⌋（偏右的那個）

圖解

dummy

→

slow→

刪除→

7 (刪除)

→

圖表展示了 [1,3,4,7,1,2,6] 的刪除過程：slow 停在節點 4（index 2），slow.next 指向中間節點 7（index 3），執行跳過後 4 直接連到 1，完成刪除。

進階觀點

💡面試追問

Q: 為什麼 slow 從 dummy 開始而不是 head？ A: 因為刪除操作需要修改「中間節點前一個」的 next 指針。slow 從 dummy 開始比 fast 慢一個位置，當 fast 到底時 slow.next 恰好是中間節點。如果 slow 也從 head 開始，停下時 slow 就是中間節點本身，無法修改前一個節點的指針。

Q: 不用 dummy 節點可以嗎？ A: 可以，但需要讓 fast 先走兩步（fast = head.next.next），然後 slow 從 head 開始。dummy 節點的好處是統一處理邏輯，不需要額外的初始化技巧。

變體題：LC 876 Middle of the Linked List（找中點不刪除）、LC 19 Remove Nth Node From End（刪倒數第 n 個）。

理解測驗

🤔 為什麼需要 dummy 節點？

🤔 對於 [1,2] 這個 Linked List，中間節點是哪個？