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

題目描述

給定一個已排序的鏈表，刪除所有出現重複的節點，僅保留原始鏈表中出現一次的數字。

示例：

• 輸入：1→2→3→3→4→4→5，輸出：1→2→5
• 輸入：1→1→1→2→3，輸出：2→3

解題思路

由於鏈表已排序，重複節點必然相鄰。使用虛擬頭節點 dummy 簡化邊界處理，雙指針遍歷：

1. pre 指向當前已確認不重複的最後一個節點（初始為 dummy）。
2. cur 用於探測下一組相同值的範圍。
3. 若 cur 與 cur.next 值不同，說明 cur 不重複，將其接在 pre 後，並移動 pre。
4. 若重複，則跳過所有相同值的節點，直接將 pre.next 指向下一個不同值的節點。
5. 最後將 pre.next = nullptr 截斷可能殘留的重複尾部。

代碼實現 (C++)

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* pre = &dummy;
        ListNode* cur = head;

        while (cur) {
            // 跳過所有重複值
            while (cur->next && cur->val == cur->next->val) {
                cur = cur->next;
            }
            // 此時 cur 是該值的最後一個節點
            if (pre->next == cur) {
                // 無重複，pre 後移
                pre = pre->next;
            } else {
                // 有重複，刪除整組
                pre->next = cur->next;
            }
            cur = cur->next;
        }
        return dummy.next;
    }
};

複雜度分析

• 時間複雜度：O(n)，單次遍歷。
• 空間複雜度：O(1)，僅使用常數額外空間。

關鍵點總結

• 虛擬頭節點統一處理頭節點被刪除的情況。
• 利用排序特性，一次跳過整個重複區間。
• 注意最後斷開尾部，防止殘留指針。