LeetCode 82. 刪除排序鏈表中的重複元素 II：三指針標記法

LeetCode 82. 刪除排序鏈表中的重複元素 II

題目要求

給定已排序鏈表，**刪除所有出現次數 > 1 的節點**，僅保留出現一次的節點。返回處理後鏈表頭。

範例

• 1→2→3→3→4→4→5 → 1→2→5
• 1→1→1→2→3 → 2→3
• 1→1→1 → NULL

三指針法邏輯

維護三指針：

• prepre：前前節點（已確定無重複的尾部）。
• pre：前節點（當前檢查組的第一個節點）。
• cur：當前節點（掃描指針）。

狀態機：

• flag = 0：當前組無重複。
• flag = 1：當前組有重複（pre 及之後同值節點均需刪除）。

完整代碼

struct ListNode* deleteDuplicates(struct ListNode* head) {
    struct ListNode *prepre = head, *pre = head, *cur = head ? head->next : NULL;
    int flag = 0;
    
    while (cur) {
        if (cur->val != pre->val && flag == 0) {      // 無重複，三指針同步前移
            prepre = pre;
            pre = cur;
            cur = cur->next;
        }
        else if (cur->val == pre->val) {              // 發現重複
            flag = 1;
            if (!cur->next) {                         // cur 是最後一個節點
                if (prepre == head && prepre->val == cur->val) // 全表重複如 1→1→1
                    return NULL;
                prepre->next = NULL;                  // 截斷尾部
                break;
            }
            cur = cur->next;
        }
        else if (cur->val != pre->val && flag == 1) { // 重複組結束，cur 為新值
            if (prepre == head && prepre->val == pre->val) { // 重複組在頭部如 2→2→2→3
                head = cur;
                prepre = head;
            } else {
                prepre->next = cur;                   // 跳過重複組
            }
            pre = cur;
            cur = cur->next;
            flag = 0;
        }
    }
    return head;
}

關鍵情況覆蓋

複雜度分析

• 時間：O(n)，單次遍歷。
• 空間：O(1)，三指針 + 標志位。

總結

刪除排序鏈表重複元素 II 核心是「識別重複組邊界並跳過」。三指針 prepre/pre/cur 配合 flag 標記重複狀態，能清晰處理「頭部重複、中間重複、尾部重複、全表重複」四大邊界情況。若覺得三指針繁瑣，亦可用「虛擬頭節點 + 雙指針預檢下一組」寫法，邏輯更統一。