題目

刪除鏈表中所有值等於 val 的節點。返回新頭指針。

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

核心難點

• 頭節點可能被刪除，需更新頭指針。
• 連續多個目標值節點。
• 釋放內存避免洩漏（C/C++ 特有）。

標準解法：雙指針 + 虛擬頭節點

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode *pre = &dummy, *cur = head;
    
    while (cur) {
        if (cur->val == val) {
            pre->next = cur->next;
            free(cur);
            cur = pre->next;
        } else {
            pre = cur;
            cur = cur->next;
        }
    }
    return dummy.next;
}

關鍵點解析

1. 虛擬頭節點：統一頭節點與普通節點的刪除邏輯，無需特判 head == val。
2. pre 指針滯後：pre 始終指向上一個非目標節點，刪除時 pre->next = cur->next 完成跳過。
3. 釋放後推進：cur = pre->next 而非 cur = cur->next，因原 cur 已釋放。
4. 返回值：dummy.next 自動指向新頭（可能為 NULL）。

遞歸寫法（參考）

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

優點：代碼極簡。缺點：棧深度 O(n)，長鏈表可能棧溢出；且釋放內存較繁瑣。

測試用例建議

• 空鏈表
• 全節點值均為目標值
• 頭/尾節點為目標值
• 連續多個目標值
• 無目標值

總結

刪除鏈表節點是指針操作基本功。虛擬頭節點技巧將邊界條件內化為統一邏輯，是鏈表題通用模板。C/C++ 還需注意手動內存管理，面試中主動提及 free/delete 會加分。