LeetCode 203 移除鏈表元素：虛擬頭節點與雙指針解法詳解

LeetCode 203 移除鏈表元素：虛擬頭節點與雙指針解法詳解

給定單鏈表頭節點 head 和整數 val，刪除鏈表中所有值等於 val 的節點，返回新頭節點。本文從基礎迭代進階到虛擬頭節點統一邏輯，分析邊界條件處理技巧。

題目範例

輸入: 1 → 2 → 6 → 3 → 4 → 5 → 6, val = 6
輸出: 1 → 2 → 3 → 4 → 5

解法一：直接迭代（處理頭節點特殊情況）

public ListNode removeElements(ListNode head, int val) {
    // 1. 處理頭節點連續等於 val 的情況
    while (head != null && head.val == val) {
        head = head.next;
    }
    if (head == null) return null; // 全部節點被刪除
    
    // 2. 遍歷後續節點
    ListNode prev = head;
    while (prev.next != null) {
        if (prev.next.val == val) {
            prev.next = prev.next.next; // 跳過目標節點
        } else {
            prev = prev.next; // 正常前進
        }
    }
    return head;
}

缺點分析

• 頭節點刪除邏輯與中間節點分離，代碼重複
• 需額外判斷 head == null
• 易漏掉連續刪除頭節點的情況

解法二：虛擬頭節點（推薦，統一邏輯）

public ListNode removeElements(ListNode head, int val) {
    // 虛擬頭節點，next 指向真實頭節點
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode prev = dummy;
    while (prev.next != null) {
        if (prev.next.val == val) {
            prev.next = prev.next.next; // 刪除
        } else {
            prev = prev.next; // 前進
        }
    }
    return dummy.next; // 返回真實頭節點
}

優勢

• 統一處理頭節點與非頭節點刪除邏輯
• 無需特殊判斷 head == null
• 代碼簡潔，不易出錯
• 通用技巧：適用於所有「可能刪除頭節點」的鏈表題

解法三：遞歸實現

public ListNode removeElements(ListNode head, int val) {
    if (head == null) return null;
    head.next = removeElements(head.next, val); // 遞歸處理後續
    return head.val == val ? head.next : head;  // 當前節點決策
}

遞歸分析

複雜度分析

關鍵測試用例

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

進階變體：移除倒數第 N 個節點 (LeetCode 19)

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode fast = dummy, slow = dummy;
    
    // fast 先走 n+1 步
    for (int i = 0; i <= n; i++) fast = fast.next;
    
    // 同步前進，fast 到達末尾時，slow 在目標節點前驅
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    slow.next = slow.next.next;
    return dummy.next;
}

總結：鏈表題核心模式

1. 虛擬頭節點：統一頭節點邏輯，消除特殊判斷
2. 雙指針：快慢指針找中點/倒數、前驅當前指針刪除
3. 就地修改：O(1) 空間，通過指針重組而非創建新節點
4. 邊界優先：空鏈表、單節點、頭尾操作、連續操作

掌握虛擬頭節點模式，能解決 80% 以上涉及節點刪除的鏈表題目，是演算法面試與工程實踐的必備技能。