19. Remove Nth Node From End of List

題目 / Problem

給定一個鏈結串列的頭節點 head，刪除從尾端數來第 n 個節點，並回傳修改後的頭節點。

Given the head of a linked list, remove the n-th node from the end of the list and return its head.

範例 / Example 1:

Input:  head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

從尾端數第 2 個是值為 4 的節點，把它刪掉。 The 2nd node from the end is the one with value 4; remove it.

其他範例 / Other examples:

Input: head = [1], n = 1   →  Output: []
Input: head = [1,2], n = 1 →  Output: [1]

限制 / Constraints: - 節點數量 sz 滿足 1 <= sz <= 30 - 0 <= Node.val <= 100 - 1 <= n <= sz（保證 n 不會超過長度 / n is always valid）

進階 / Follow up: 能不能只走訪一次（one pass）就完成？

名詞解釋 / Glossary

• 鏈結串列 / Linked list：由一連串「節點」組成的資料結構，每個節點存一個值，以及一個指向下一個節點的指標。最後一個節點指向 NULL（空）。A chain of "nodes", each holding a value and a pointer to the next node; the last node points to NULL.
• 節點 / Node：串列中的一個元素，這題長這樣：struct ListNode { int val; struct ListNode *next; };。One element of the list.
• 指標 / Pointer：一個存著「記憶體位址」的變數。p->next 表示「順著指標 p 找到節點，再取它的 next 欄位」。A variable holding a memory address; p->next means "follow p to its node, then read the next field".
• 虛擬頭節點 / Dummy node：一個放在真正頭節點前面的假節點。它讓「刪除第一個節點」和「刪除中間節點」變成同一種寫法，避免特殊處理。A fake node placed before the real head so that deleting the first node uses the same code as deleting any other node.
• 雙指針 / Two pointers：同時使用兩個指標走訪，透過固定它們之間的「間距」來一次走訪解決問題。Using two pointers with a fixed gap between them to solve the problem in a single pass.
• 一次走訪 / One pass：整個串列只從頭到尾掃過一遍，不重複掃。Scanning the list front-to-back only once.

思路

最直覺的做法是「兩次走訪」：先從頭走到尾，數出串列總長度 L，那麼「從尾端數第 n 個」其實就是「從頭數第 L - n + 1 個」。知道位置後，再走一次找到它前面的節點，把指標繞過要刪的節點即可。這個方法正確，但要走兩趟。進階題問我們能不能只走一趟，這就要用到雙指針技巧。

雙指針的關鍵想法是：先讓一個 fast 指標從頭往前走 n 步，這樣 fast 和還停在起點的 slow 之間就固定隔了 n 個節點。接著讓兩個指標一起往前走，直到 fast 走到最後（NULL）。因為它們間距永遠是 n，當 fast 到終點時，slow 剛好停在「要刪節點的前一個」。這時把 slow->next 改成 slow->next->next，就繞過並刪掉了目標節點。為了讓「刪除頭節點」也能用同一套邏輯（例如 [1], n=1 要刪掉頭本身），我們在真正的頭前面加一個虛擬頭節點 dummy，讓 slow 從 dummy 出發，這樣它永遠有「前一個節點」可站，程式碼不用為刪頭寫特例。

The brute-force approach is two passes: walk once to count the total length L, then note that "the n-th node from the end" is the same as "the (L - n + 1)-th node from the front". Walk again to reach the node just before it and splice it out. Correct, but it scans twice. The follow-up asks for one pass, which is where two pointers shines. Advance a fast pointer n steps ahead first, creating a fixed gap of n nodes between fast and a slow pointer still at the start. Then move both together until fast falls off the end (NULL). Since the gap is always n, when fast reaches the end, slow sits exactly on the node before the one to delete, so slow->next = slow->next->next removes it. To handle deleting the head itself (e.g. [1], n=1) with the same code, we prepend a dummy node and start slow there, guaranteeing slow always has a valid "previous node" and avoiding a special case.

逐步走查 / Walkthrough

以 head = [1,2,3,4,5], n = 2 為例。加上虛擬頭後串列是 dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL。

Step A — 先讓 fast 走 n = 2 步 / Advance fast by n = 2 steps:

Step B — slow 從 dummy 出發，兩者一起走到 fast == NULL / Move both until fast is NULL:

Step C — 刪除 / Delete: slow 停在 node 3，要刪的是 slow->next（node 4）。執行 slow->next = slow->next->next，讓 node 3 直接指向 node 5。

結果 / Result：1 -> 2 -> 3 -> 5，回傳 dummy->next。✅

Solution — C

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

Solution — C++

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

複雜度 / Complexity

• Time: O(sz) — sz 是串列長度。fast 從頭走到尾總共前進 sz 步，slow 跟著走一段，整個過程只掃一遍串列。fast traverses the whole list once (sz steps); everything is a single pass.
• Space: O(1) — 只用了 dummy、fast、slow、target 幾個固定的指標變數，與串列長度無關。Only a constant number of pointer variables are used, regardless of list length.

Pitfalls & Edge Cases

• 刪除頭節點 / Deleting the head：像 [1], n=1 要刪掉頭本身。若沒有虛擬頭，slow 就沒有「前一個節點」可站，得寫特例。虛擬頭讓 slow 從 dummy 出發，一律用 slow->next = slow->next->next 處理。The dummy node removes the need to special-case removing the first node.
• 間距要正好 n / Gap must be exactly n：fast 要走 n 步（不是 n-1 或 n+1），且 slow 從 dummy 出發。這個組合才能保證 fast 到 NULL 時 slow 停在待刪節點的前一個。Off-by-one here deletes the wrong node — pair "fast walks n steps" with "slow starts at dummy".
• 停止條件是 fast == NULL / Stop when fast == NULL：要停在 NULL，不是最後一個節點。若寫成 fast->next != NULL 會少走一步，刪錯節點。Loop until fast is null, not until its next is null.
• 記憶體釋放 / Freeing memory：C 用 free、C++ 用 delete 釋放被刪節點。LeetCode 不釋放也能通過，但養成好習慣可避免記憶體洩漏。務必先用 target 記住節點「再」改指標，否則就找不到它了。Save the node before rewiring, then free it.
• 不需擔心 n 越界 / No need to guard n：題目保證 1 <= n <= sz，所以 fast 走 n 步不會衝出串列。The constraints guarantee n is valid, so the n-step advance never overruns.