2095. Delete the Middle Node of a Linked List

題目 / Problem

中文： 給你一個鏈結串列的頭節點 head。請刪除其中的中間節點，並回傳修改後串列的頭節點。

對於一個長度為 n 的鏈結串列，中間節點是從頭開始、用 0-based（從 0 開始數）索引的第 ⌊n / 2⌋ 個節點。⌊x⌋ 表示不超過 x 的最大整數（也就是向下取整）。

• 當 n = 1, 2, 3, 4, 5 時，中間節點的索引分別是 0, 1, 1, 2, 2。

English: You are given the head of a linked list. Delete the middle node and return the head of the modified list.

For a list of size n, the middle node is the node at 0-based index ⌊n / 2⌋ (the largest integer ≤ n / 2, i.e. integer division).

• For n = 1, 2, 3, 4, 5 the middle indices are 0, 1, 1, 2, 2.

約束 / Constraints - 節點數量範圍 [1, 10^5] / The list has between 1 and 10^5 nodes. - 1 <= Node.val <= 10^5.

範例 / Worked example

Input:  head = [1,3,4,7,1,2,6]   (n = 7)
中間索引 = ⌊7/2⌋ = 3 → 值為 7 的節點 / index 3 holds value 7
Output: [1,3,4,1,2,6]

名詞解釋 / Glossary

• 鏈結串列 / Linked list：一串「節點」串起來的資料結構。每個節點存一個值 val 和一個指向「下一個節點」的指標 next。最後一個節點的 next 是 NULL（空）。和陣列不同，它無法用索引 O(1) 直接跳到第 k 個，只能從頭一個一個走。
• 節點 / Node：串列裡的一個元素，包含 val（資料）與 next（指向下一個節點的指標）。
• 指標 / Pointer：一個存放「某個節點記憶體位址」的變數。p->next 表示「沿著 p 走到下一個節點」。
• 雙指針（快慢指針）/ Two pointers (fast & slow)：同時用兩個指標走串列，一個每次走 1 步（慢），一個每次走 2 步（快）。當快指針到底時，慢指針剛好在中間。這是一次走完就找到中點的技巧。
• 原地修改 / In-place：不另外開新串列，直接改動原本節點的 next 連結來達成刪除，額外空間是 O(1)。
• 刪除節點 / Deleting a node：把「被刪節點的前一個節點」的 next，改成指向「被刪節點的後一個節點」，這樣中間那個就被跳過了。被跳過的節點若是用 malloc 配置的，應該 free 釋放避免記憶體洩漏。
• 虛擬頭節點（dummy node）/ Dummy node：在真正的 head 前面放一個假的節點，讓「刪除 head」和「刪除中間」可以用同一套邏輯處理，省去特判。本題另有更簡單的寫法，不一定需要它。

思路

中文： 最直覺的暴力解是「走兩趟」：第一趟從頭走到尾，數出總長度 n；算出中間索引 m = n / 2（整數除法自動向下取整）；第二趟再從頭走 m - 1 步，停在中間節點的「前一個」，把它的 next 接到「中間節點的後一個」即可刪除。這個方法完全正確，時間是 O(n)，但要掃兩遍串列。

能不能只走一遍就找到中點？可以，這就是快慢指針。讓 slow 每次走 1 步、fast 每次走 2 步，兩者從同一起點出發。因為 fast 的速度是 slow 的兩倍，當 fast 走到串列尾端時，slow 剛好只走了一半，也就是停在中間節點上。這正好對應提示裡「速度兩倍、同時間走兩倍距離」的想法。

但要「刪除」中間節點，光知道中間節點還不夠——我們需要它「前一個」節點，才能改連結跳過它。所以再用一個 prev 指標永遠記住 slow 的上一個位置。當迴圈結束、slow 指向中間時，prev->next 就改成 slow->next，把中間節點繞過去，然後 free 掉它。注意 n = 1 的特例：只有一個節點時中間就是 head，刪掉後串列變空，要回傳 NULL。

關鍵迴圈條件是 fast != NULL && fast->next != NULL，確保 fast 一次跳兩步時不會越界。迴圈結束時 slow 必然停在索引 ⌊n/2⌋，這個不變量（invariant）讓我們不用先算長度就能精準命中題目定義的中間節點。

English: The brute-force idea is two passes. First walk the whole list to count its length n; the middle index is m = n / 2 (integer division already floors it). Then walk again from the head, stopping m - 1 steps in at the node before the middle, and splice it out by pointing its next at the middle's successor. Correct, O(n) time, but it scans the list twice.

We can find the middle in a single pass using the fast & slow pointers trick. Move slow one step and fast two steps each iteration, both starting at the head. Since fast covers twice the distance, by the time fast reaches the end, slow has gone exactly halfway — landing on the middle node. This is exactly the hint's "twice the speed covers twice the distance" observation.

To delete the middle, knowing it isn't enough — we need the node before it so we can rewire the link to skip it. So we keep a prev pointer trailing one step behind slow. When the loop ends and slow sits on the middle, we set prev->next = slow->next to bypass it, then free the removed node. Watch the n = 1 case: the only node is the middle, deleting it leaves an empty list, so return NULL.

The loop condition fast != NULL && fast->next != NULL guarantees the two-step jump never runs off the end. The invariant is that when the loop stops, slow is exactly at index ⌊n/2⌋, which lets us hit the problem's defined middle without ever computing the length.

逐步走查 / Walkthrough

輸入 / Input: head = [1,3,4,7,1,2,6]，索引 0..6，預期刪除索引 3（值 7）。

我們用 prev（慢指針的前一個）、slow（慢，每步 +1）、fast（快，每步 +2）。初始 prev = NULL，slow = fast = 節點0。迴圈條件 fast && fast->next。

迴圈結束時 slow 停在 idx3（值 7），正是中間節點；prev 停在 idx2（值 4）。 When the loop ends, slow is at index 3 (value 7) — the middle — and prev is at index 2 (value 4).

刪除步驟 / Deletion: - prev->next = slow->next：讓 idx2(4) 直接指向 idx4(1)，跳過 idx3(7)。 Point node 4 directly at node 1, skipping the 7. - free(slow)：釋放被刪節點的記憶體 / free the removed node. - 回傳 head（仍是 idx0）/ return the unchanged head.

結果 / Result: [1,3,4,1,2,6] ✅

Solution — C

/*
 * 演算法 / Algorithm:
 * 用快慢指針一趟找到中間節點：slow 每步走 1、fast 每步走 2。
 * Fast & slow pointers in one pass: when fast hits the end, slow is the middle.
 * 同時用 prev 記住 slow 的前一個節點，最後 prev->next = slow->next 跳過並 free 掉中間節點。
 * Keep prev one step behind slow, then splice the middle out and free it.
 */

// LeetCode 已定義的節點結構（這裡列出僅供理解，提交時無需重寫）
// The node struct LeetCode already provides (shown only for clarity):
// struct ListNode { int val; struct ListNode *next; };

struct ListNode* deleteMiddle(struct ListNode* head) {
    // 特例：只有一個節點時，中間就是 head，刪掉後變空串列，回傳 NULL
    // Edge case: a single node IS the middle; deleting it leaves an empty list
    if (head->next == NULL) {
        free(head);          // 釋放這個節點的記憶體，避免洩漏 / free it to avoid a memory leak
        return NULL;         // 空串列用 NULL 表示 / an empty list is represented by NULL
    }

    struct ListNode* prev = NULL;   // slow 的前一個節點，初始還沒有 / node before slow; none yet
    struct ListNode* slow = head;   // 慢指針，每次走 1 步 / slow pointer, advances 1 step
    struct ListNode* fast = head;   // 快指針，每次走 2 步 / fast pointer, advances 2 steps

    // 只要 fast 還能安全往前跳兩步就繼續走
    // Keep going while fast can safely jump two more steps
    while (fast != NULL && fast->next != NULL) {
        prev = slow;            // prev 跟上 slow 目前的位置 / prev catches up to slow
        slow = slow->next;      // slow 前進 1 步（-> 是「沿指標到下一節點」）/ slow moves 1 node forward
        fast = fast->next->next; // fast 前進 2 步 / fast moves 2 nodes forward
    }
    // 迴圈結束：slow 停在索引 ⌊n/2⌋，即題目定義的中間節點
    // Loop done: slow sits at index ⌊n/2⌋ — the middle node

    prev->next = slow->next;    // 讓中間的前一個直接指向中間的後一個，跳過中間 / bypass the middle
    free(slow);                 // 釋放被刪除節點的記憶體 / free the deleted node
    return head;                // head 沒變，直接回傳 / head is unchanged, return it
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 快慢指針一趟定位中間節點（slow 走 1、fast 走 2），prev 跟在 slow 後面。
 * One-pass fast & slow pointers find the middle; prev trails slow by one node.
 * 最後把 prev->next 接到 slow->next 跳過中間節點，並 delete 釋放它。
 * Splice prev->next to slow->next to skip the middle, then delete it.
 */

// LeetCode 提供的節點結構 / Node struct provided by LeetCode:
// struct ListNode { int val; ListNode *next; ListNode(int x): val(x), next(nullptr) {} };

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        // 特例：只有一個節點 → 刪掉後回傳 nullptr（C++ 的空指標）
        // Edge case: single node → delete it and return nullptr (C++'s null pointer)
        if (head->next == nullptr) {
            delete head;          // delete 釋放 new 出來的節點 / delete frees the heap node
            return nullptr;
        }

        ListNode* prev = nullptr; // slow 的前一個節點 / node just before slow
        ListNode* slow = head;    // 慢指針，每次 +1 / slow, advances by 1
        ListNode* fast = head;    // 快指針，每次 +2 / fast, advances by 2

        // fast 能再跳兩步就繼續 / loop while fast can take two more steps
        while (fast != nullptr && fast->next != nullptr) {
            prev = slow;            // prev 記住 slow 現在的位置 / remember slow's current node
            slow = slow->next;      // slow 前進 1 步 / slow moves forward one node
            fast = fast->next->next;// fast 前進 2 步 / fast moves forward two nodes
        }
        // 此時 slow 正好在中間節點（索引 ⌊n/2⌋）/ now slow is exactly the middle (index ⌊n/2⌋)

        prev->next = slow->next;    // 重接連結，跳過中間節點 / rewire to skip the middle node
        delete slow;                // 釋放被刪節點，避免記憶體洩漏 / free it to avoid a leak
        return head;                // 回傳未改動的 head / return the unchanged head
    }
};

複雜度 / Complexity

• Time: O(n) — 快指針一次最多掃到串列尾端，慢指針只走一半；總步數與節點數 n 成正比，只走一趟。最後刪除是 O(1)。/ The fast pointer reaches the end in one pass; total work scales linearly with the number of nodes n. The splice + free is O(1).
• Space: O(1) — 只用了 prev、slow、fast 三個指標變數，與 n 無關，原地修改不另開串列。/ Only three pointer variables regardless of list length; we modify links in place.

Pitfalls & Edge Cases

• 單一節點 / Single node (n = 1)：中間就是 head，刪掉後串列為空。若不特判，prev 會是 NULL，執行 prev->next 會崩潰。程式一開始就用 head->next == NULL 攔截並回傳 NULL。/ The only node is the middle; without the early return, prev stays null and prev->next crashes.
• 忘記用 prev / Forgetting prev：只找到中間節點是不夠的，單向串列無法回頭找前一個。必須在走的過程中用 prev 記住前一節點，才能重接連結。/ A singly linked list can't go backwards, so you must track the predecessor while walking.
• 迴圈條件寫錯 / Wrong loop condition：用 fast->next->next 跳兩步前，必須先確認 fast 與 fast->next 都不是 NULL，否則對 NULL 解參考會崩潰。條件 fast && fast->next 正是為此。/ Both fast and fast->next must be non-null before the double jump, or you dereference null.
• 記憶體洩漏 / Memory leak：被跳過的節點若不 free（C）或 delete（C++），記憶體就回收不了。雖然 LeetCode 不會因此判錯，但這是良好習慣。/ The bypassed node should be freed/deleted; leaking it is poor practice even if LeetCode tolerates it.
• 回傳值搞錯 / Returning the wrong thing：除了 n = 1，head 永遠不變，要回傳原本的 head 而不是 slow 或 prev。/ Except for n = 1, the head never changes — return the original head, not slow or prev.
• 整數索引理解 / Off-by-one on the middle：中間是 ⌊n/2⌋（0-based）。快慢指針從 head 同起點出發、條件設為 fast && fast->next，自然落在這個索引，不需要額外加減。/ Starting both pointers at head with this condition lands slow exactly on ⌊n/2⌋ — no manual offset needed.