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