LeetCode 19. 刪除鏈表倒數第 N 個節點：雙指針一次遍歷

LeetCode 19. 刪除鏈表倒數第 N 個節點：雙指針一次遍歷

給定單鏈表頭節點 head 和整數 n，刪除倒數第 n 個節點，返回頭節點。要求一次遍歷，O(1) 空間。

雙指針核心技巧

1. 兩指針 fast、slow 初始指向頭節點。
2. fast 先走 n 步。
3. 若 fast 走到 NULL，說明刪除的是頭節點，直接返回 head->next。
4. 否則 fast 和 slow 同步前進，直到 fast->next == NULL。
5. 此時 slow 指向待刪節點的前驅，執行 slow->next = slow->next->next。

代碼實現

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode *fast = head, *slow = head;
    // fast 先走 n 步
    while (n--) fast = fast->next;
    // 刪除頭節點
    if (!fast) return head->next;
    // 同步前進直到 fast 到達尾節點
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    // 刪除 slow->next
    slow->next = slow->next->next;
    return head;
}

圖解過程

List: 1→2→3→4→5, n=2
fast 先走 2 步 → 指向 3
同步前進：
  fast=4, slow=2
  fast=5, slow=3  (fast->next 為 NULL 停止)
slow 指向 3，刪除其 next (4)
結果：1→2→3→5

邊界情況

• n = 鏈表長度：刪除頭節點，fast 走完即為 NULL，直接返回 head->next。
• n = 1：刪除尾節點，fast 走 1 步指向尾，同步循環不執行，slow 停在倒數第二個節點，正常刪除。
• 單節點鏈表 n=1：fast 走 1 步為 NULL，返回 NULL。

複雜度

• 時間 O(L)，L 為鏈表長度（單次遍歷）。
• 空間 O(1)。