/*
 * 演算法 / Algorithm: 雙指針一次走訪 / two-pointer single pass.
 * fast 先走 n 步製造間距，再與 slow 同步前進；fast 到底時 slow 停在待刪節點的前一個。
 * 使用虛擬頭節點統一處理「刪除頭節點」的情況。
 * fast leads by n, both advance together; a dummy head unifies the delete-head case.
 */

// LeetCode 已定義 / LeetCode already defines:
// struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 建立虛擬頭節點，其 next 指向真正的 head / dummy node pointing to the real head.
        ListNode dummy(0);          // 用建構子把 val 設為 0 / construct a node with val 0.
        dummy.next = head;          // 接在整串前面 / attach before the list.

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

        // fast 先走 n 步 / advance fast by n steps.
        for (int i = 0; i < n; ++i) {
            fast = fast->next;      // 沿 next 前進 / follow the next pointer.
        }

        // 兩指針同步前進，直到 fast 為 nullptr / move both until fast is nullptr.
        while (fast != nullptr) {
            fast = fast->next;      // fast 前進 / step fast.
            slow = slow->next;      // slow 前進，間距保持 n / slow keeps the gap of n.
        }

        // slow->next 即為待刪節點 / slow->next is the node to remove.
        ListNode* target = slow->next;      // 記住它以便釋放 / keep it to delete.
        slow->next = slow->next->next;      // 繞過待刪節點 / splice it out.
        delete target;                      // 釋放記憶體，避免洩漏 / free memory to avoid a leak.

        // 回傳可能已改變的新頭 / return the possibly-new head.
        return dummy.next;
    }
};