LeetCode 19：刪除鏈表的倒數第 N 個節點——雙指針單次遍歷解法

題目描述

給定單鏈表頭節點，刪除倒數第 n 個節點並返回新頭節點。n 保證合法。要求單次遍歷完成。

雙指針技巧

使用 fast、slow 兩指針：

1. fast 先走 n 步。
2. 之後 fast、slow 同步前進，直到 fast 到達尾部（fast->next == nullptr）。
3. 此時 slow 指向待刪除節點的前驅節點。
4. 執行 slow->next = slow->next->next 完成刪除。

為統一處理頭節點被刪除情況，引入 虛擬頭節點 dummy。

C++ 代碼

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode *fast = &dummy, *slow = &dummy;

        for (int i = 0; i < n; ++i) fast = fast->next;

        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* toDel = slow->next;
        slow->next = toDel->next;
        delete toDel;  // 若需釋放記憶體
        return dummy.next;
    }
};

關鍵點

• 虛擬頭節點消除「刪除頭節點」的特判邏輯。
• fast 先走 n 步而非 n+1，配合 while(fast->next) 使 slow 停在前驅。
• 單次遍歷，時間 O(L)，空間 O(1)。

總結

雙指針間距固定為 n，利用尾部作為基準反向定位，是解決鏈表倒數問題的通用模板。