LeetCode 刪除鏈表中值為 val 的所有節點：迭代法與虛擬頭節點技巧

題目描述

給定單鏈表頭節點 head 和整數 val，刪除鏈表中所有值等於 val 的節點，返回新頭節點。

示例：1 → 2 → 6 → 3 → 4 → 5 → 6, val = 6 → 1 → 2 → 3 → 4 → 5

核心難點：頭節點可能被刪除

若頭節點值為 val，頭指針需後移；可能連續多個頭節點需刪除。直接處理需特判，代碼繁瑣。

技巧：虛擬頭節點

創建一個虛擬節點 dummy 指向 head，統一處理「前驅節點的 next 指向當前節點」的邏輯，無需特判頭節點。

迭代解法（推薦）

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode *prev = &dummy, *curr = head;

    while (curr) {
        if (curr->val == val) {
            // 刪除 curr：prev->next 跳過 curr
            struct ListNode* del = curr;
            prev->next = curr->next;
            curr = curr->next;
            free(del);  // C 語言釋放記憶體；C++ 用 delete
        } else {
            // 保留 curr：前移 prev 和 curr
            prev = curr;
            curr = curr->next;
        }
    }
    return dummy.next;
}

關鍵點圖解

初始：dummy → 1 → 2 → 6 → 3 → 4 → 5 → 6
           ↑    ↑
         prev curr

檢測到 6：prev->next = curr->next (跳過 6)
         刪除 6，curr 前移

繼續遍歷直到結束
結果：dummy → 1 → 2 → 3 → 4 → 5

遞歸解法（簡潔但有棧溢出風險）

struct ListNode* removeElements(struct ListNode* head, int val) {
    if (!head) return NULL;
    head->next = removeElements(head->next, val);
    return head->val == val ? head->next : head;
}

複雜度對比

常見錯誤與調試技巧

1. 忘記釋放記憶體：C/C++ 手動管理內存，刪除節點必須 free/delete
2. prev 不前移：刪除節點時 prev 保持不變，只有保留節點時才 prev = curr
3. 返回錯誤頭指針：必須返回 dummy.next，而非 head
4. 連續刪除邏輯錯誤：虛擬頭節點天然解決此問題

延伸：刪除重複值節點（LeetCode 82/83）

• 83 刪除重複值，保留一個：同樣用虛擬頭，檢測 curr->val == curr->next->val
• 82 刪除所有重複值節點：需記錄重複值範圍，批量跳過

虛擬頭節點是鏈表題目的「萬金油」，將邊界條件內化為統一邏輯，極大降低出錯率，是面試與工程中的必備技巧。