/*
 * 演算法 / Algorithm: 雙指針一次走訪 / two-pointer single pass.
 * 讓 fast 先走 n 步製造間距，再兩指針同步前進；fast 到底時 slow 停在
 * 待刪節點的前一個，改指標繞過它即可。虛擬頭讓刪除頭節點無需特例。
 * Advance fast by n, then move both together; when fast hits the end,
 * slow is just before the target. A dummy head removes the delete-head edge case.
 */

// LeetCode 已定義 / LeetCode already defines:
// struct ListNode { int val; struct ListNode *next; };

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    // 建立虛擬頭節點，next 先指向真正的 head / dummy node whose next is the real head.
    // 這樣「刪除第一個節點」就跟刪除其他節點寫法一致 / makes deleting the head uniform.
    struct ListNode dummy;          // 放在堆疊上的一個節點 / a node on the stack.
    dummy.next = head;              // 讓 dummy 接在整串前面 / attach dummy before the list.

    struct ListNode *fast = dummy.next;  // fast 從真正的 head 出發 / fast starts at the real head.
    struct ListNode *slow = &dummy;      // slow 從 dummy 出發（取位址用 & ）/ slow starts at dummy (& = address-of).

    // 讓 fast 先往前走 n 步，製造 n 的間距 / move fast n steps ahead to create a gap of n.
    for (int i = 0; i < n; i++) {
        fast = fast->next;          // fast 沿著 next 指標往前 / follow the next pointer forward.
    }

    // 兩指針一起走，直到 fast 走出串列（變成 NULL）/ move both until fast falls off the end.
    while (fast != NULL) {
        fast = fast->next;          // fast 前進一步 / step fast forward.
        slow = slow->next;          // slow 同步前進，間距保持 n / slow keeps the gap of n.
    }

    // 此時 slow->next 正是要刪的節點 / slow->next is exactly the node to remove.
    struct ListNode *target = slow->next;   // 記住待刪節點，稍後釋放記憶體 / remember it to free later.
    slow->next = slow->next->next;          // 繞過待刪節點：指向它的下一個 / splice it out.
    free(target);                           // 歸還記憶體，避免記憶體洩漏 / return memory to avoid a leak.

    // 回傳新的頭：dummy.next（可能已因刪頭而改變）/ return dummy.next, the possibly-new head.
    return dummy.next;
}