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

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

給定一個單鏈表，要求刪除倒數第 n 個節點並返回頭節點。例如鏈表 1→2→3→4→5 中刪除倒數第 2 個節點後變為 1→2→3→5。題目保證 n 始終有效，並挑戰在一次遍歷中完成。

核心思路：快慢指針

利用兩個指針 left 和 right 同時從頭節點出發。先讓 right 向前移動 n 步，此時兩指針相距 n 個節點。隨後雙指針同步前進，當 right 到達末尾（right.next == null）時，left 恰好指向待刪除節點的前驅節點，直接修改 left.next = left.next.next 即可完成刪除。

邊界情況處理

若 right 移動 n 步後直接變為 null，說明要刪除的是頭節點，直接返回 head.next。

代碼實現

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode left = head;
        ListNode right = head;
        for (int i = 0; i < n; i++) {
            right = right.next;
        }
        if (right == null) {
            return head.next; // 刪除頭節點
        }
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return head;
    }
}

複雜度分析

• 時間複雜度：O(L)，L 為鏈表長度，僅單次遍歷。
• 空間複雜度：O(1)，只使用常數額外空間。

此解法滿足「一次遍歷」要求，且代碼簡潔易懂，是面試與競程中的經典寫法。