LeetCode 203. 移除鏈表元素：虛擬頭節點法 C 語言標準解法

LeetCode 203. 移除鏈表元素：虛擬頭節點法 C 語言標準解法

刪除單鏈表中所有值等於 `val` 的節點。本文推薦使用**虛擬頭節點**統一處理頭節點刪除邊界情況，給出清晰的雙指針遍歷刪除邏輯，並分析常見錯誤與內存管理細節。

題目大意

• 輸入：單鏈表頭指針 `head`，目標值 `val`。
• 操作：刪除所有 `node->val == val` 的節點。
• 輸出：修改後的鏈表頭指針。
• 示例：1→2→6→3→4→5→6, val=6 → 1→2→3→4→5。

核心難點：頭節點刪除

若頭節點值等於 `val`，需更新 `head` 指針。常規寫法需單獨處理頭節點，代碼冗餘。
**虛擬頭節點** 技巧：在真實頭節點前創建一個 `dummy` 節點，`dummy->next = head`。統一從 `dummy` 開始遍歷，刪除邏輯一致，最後返回 `dummy->next`。

標準 C 語言實現

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) {
    // 1. 創建虛擬頭節點
    struct ListNode dummy;
    dummy.next = head;
    dummy.val = 0; // 值無關緊要

    // 2. 雙指針遍歷：pre 指向當前檢查節點的前驅
    struct ListNode *pre = &dummy;
    struct ListNode *cur = head;

    while (cur != NULL) {
        if (cur->val == val) {
            // 刪除 cur：pre->next 跳過 cur
            pre->next = cur->next;
            // 可選：free(cur) 釋放內存（題目通常不管理）
            cur = pre->next; // cur 後移，pre 不動
        } else {
            // 正常後移
            pre = cur;
            cur = cur->next;
        }
    }

    // 3. 返回真實頭節點
    return dummy.next;
}

關鍵點解析

• 虛擬頭節點在棧上：`struct ListNode dummy;` 無需 `malloc`，函數返回前自動銷毀，無內存洩漏。
• pre 指針意義：永遠指向「待檢查節點的前一個節點」，刪除時只需 `pre->next = cur->next`。
• 刪除後指針更新：`cur = pre->next`；`pre` 保持不變，因為下一個節點可能也需刪除（連續相同值）。
• 內存釋放：LeetCode 環境通常不要求 `free`，但工程代碼中應 `free(cur)` 後再移動指針（需臨時保存 `next`）。

遞歸版（簡潔但棧深度 O(n)）

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. **忘記處理頭節點刪除**：導致頭節點值為 `val` 時未被移除。
2. **刪除後 `pre` 也後移**：`pre = cur; cur = cur->next;` 錯誤，應 `cur = pre->next`。
3. **未保存 `next` 就 `free`**：`free(cur); cur = cur->next;` 野指針讀取。正確：`tmp=cur; cur=cur->next; free(tmp);`。
4. **返回 `head` 而非 `dummy.next`**：頭節點被刪除時 `head` 已失效。

總結

移除鏈表元素是鏈表基本操作核心考點。**虛擬頭節點 + 雙指針** 是處理頭節點邊界條件的標準模板，邏輯統一、代碼簡潔、無特殊情況分支。掌握此模板，可直接應用於「刪除倒數第 N 個」、「分隔鏈表」等眾多鏈表題。