/*
 * 演算法 / 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
    }
};