LeetCode 刪除鏈表倒數第 N 個節點：雙指針法深度解析

終於遇到與數據結構相關的題目了，這意味著複雜度開始提升。今天來攻克 LeetCode 經典題目——「刪除鏈表的倒數第 N 個節點」。直觀想法是先遍歷一次求長度，再定位刪除位置，但這需要兩次遍歷。有沒有一次遍歷就能搞定的巧妙方法？答案是肯定的，雙指針法（快慢指針）正是為此而生。

核心思路：快慢指針的協作

我們維護兩個指針 fast 和 slow，初始都指向頭結點。關鍵在於 fast 先走 n + 1 步，然後兩個指針同步前進，直到 fast 走到鏈表末尾（NULL）。此時 slow 恰好指向「待刪除節點的前一個節點」，直接修改 slow->next 即可完成刪除。

為什麼是 n + 1 步？

若 fast 只走 n 步，當 fast 到達尾部時，slow 指向的正是「待刪除節點」本身。在單鏈表中，要刪除一個節點必須知道其前驅節點，否則還得再遍歷一遍找前驅，得不償失。讓 fast 多走一步，slow 就會停在前驅位置，一次遍歷搞定一切。

邊界情況處理：刪除頭結點

當鏈表長度恰好等於 n 時，待刪除節點就是頭結點。代碼中通過檢查 fast 走完 n+1 步後的剩餘步數 m 來判斷：

• m > 1：鏈表長度不足 n，直接返回 NULL
• m == 1：說明 fast 走到頭還差一步，即待刪除的是頭結點，直接 head = head->next
• 其他情況：slow 指向前驅，正常刪除

完整 C++ 實現

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (head == NULL || n <= 0) return NULL;
        
        ListNode *fast = head, *slow = head;
        int m = n + 1;  // 尋找待刪除節點的前驅
        
        // fast 先走 n+1 步
        while (fast && m) {
            fast = fast->next;
            --m;
        }
        
        // 邊界判斷
        if (m > 1) return NULL;          // 長度不足
        if (m == 1) {                    // 刪除頭結點
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
            return head;
        }
        
        // 同步前進，直到 fast 到達末尾
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        
        // 刪除目標節點
        ListNode* toDel = slow->next;
        slow->next = slow->next->next;
        delete toDel;
        return head;
    }
};

這道題展示了雙指針技巧在鏈表操作中的威力：通過「預先拉開距離 + 同步移動」將兩次遍歷壓縮為一次，時間複雜度 O(L)，空間複雜度 O(1)，是面試和競賽中的必備技法。