82. Remove Duplicates from Sorted List II

題目 / Problem

中文： 給定一個已排序（升序）鏈結串列的頭節點 head，請刪除所有含有重複數字的節點，只留下原本就唯一（不重複）的數字。回傳處理後、仍保持排序的鏈結串列。

注意重點：不是「重複的只留一個」，而是「只要重複過，就全部刪光」。

English: Given the head of a sorted (ascending) linked list, delete every node whose value appears more than once, keeping only the numbers that were distinct in the original list. Return the resulting list, still sorted.

Key point: this is not "keep one copy of each duplicate" — if a value repeats at all, all of its nodes are removed.

Constraints / 限制： - 節點數量在 [0, 300]（可能是空串列）/ Number of nodes is in [0, 300] (list may be empty). - -100 <= Node.val <= 100 - 串列保證已按升序排好 / The list is guaranteed sorted in ascending order.

Worked example / 範例：

Input:  head = [1,2,3,3,4,4,5]
Output: [1,2,5]

3 出現兩次、4 出現兩次，所以 3 和 4 的所有節點都被刪除，只剩下唯一的 1, 2, 5。 3 appears twice and 4 appears twice, so every 3 and 4 node is removed, leaving the unique values 1, 2, 5.

名詞解釋 / Glossary

• 鏈結串列 / linked list：一種資料結構，每個節點 (node) 存一個值 val 和一個指向下一個節點的指標 next。要走訪它必須從頭一路沿著 next 走，不能像陣列那樣用索引直接跳。 / A chain of nodes where each node holds a value and a pointer to the next node. You traverse it by following next pointers; there is no random indexing.
• 節點 / node：串列裡的一個元素，包含 val（值）和 next（下一個節點的位址）。 / One element of the list, containing a value and a next pointer to the following node.
• 指標 / pointer：一個存放「記憶體位址」的變數。p->next（C）或 p->next（C++）表示「p 所指節點的 next 欄位」。 / A variable holding a memory address. p->next means "the next field of the node that p points to."
• 虛擬頭節點 / dummy node：我們自己額外建立、放在真正 head 前面的一個假節點。因為真正的 head 本身也可能要被刪除，有了 dummy 就能用統一的方式處理所有節點，回傳時只要回傳 dummy->next。 / An extra fake node we place before the real head. Since the real head might itself need deleting, the dummy lets us handle every node uniformly; we return dummy->next at the end.
• 雙指針 / two pointers：用兩個指標協作走訪串列。這裡一個 prev 停在「已確認保留的最後一個節點」，另一個 cur 向前探查重複區段。 / Using two coordinated pointers; here prev sits on the last confirmed-kept node while cur scans ahead over duplicate runs.
• 原地修改 / in-place：不另外開一個新串列，直接調整原串列的指標來得到答案，額外空間為常數。 / Modifying the original list's pointers directly instead of building a new list, using only constant extra space.
• 記憶體釋放 / free (C)：C 語言中，被刪除的節點若是動態配置的，用 free() 歸還記憶體以免洩漏。LeetCode 判題不強制，但這是好習慣。 / In C, released deleted nodes with free() to avoid memory leaks; good practice even if the judge doesn't require it.

思路

中文： 最直覺的暴力想法是「先數每個值出現幾次，再刪掉出現超過一次的」——例如用一個雜湊表或計數陣列統計，然後第二次走訪把計數大於 1 的節點刪掉。這確實可行，但需要兩趟走訪和額外空間。既然題目已經保證串列「排好序」，重複的數字一定是連續排在一起的（像 3,3 或 4,4,4），我們就能用更聰明的單趟做法。

關鍵想法：用兩個指標。因為連 head 都可能要刪，我們先建一個 虛擬頭節點 dummy，讓 dummy->next = head，這樣就不必為「刪掉第一個節點」寫特例。指標 prev 從 dummy 出發，代表「目前已確認要保留、且串接無誤的最後一個節點」；另一個指標 cur 負責往前探查。每一步檢查 cur 和 cur->next 的值是否相同：

• 如果相同，代表遇到一段重複區段。就讓 cur 一直往前走，直到跳過所有等於這個值的節點。然後把 prev->next 直接接到這段之後（prev->next = cur->next），等於一次剪掉整段重複。注意此時 prev 不動，因為我們還不知道下一個節點是否也是重複的。
• 如果不同，代表 cur 是個「目前看來唯一」的節點，可以安心保留。就把 prev 前進到 cur（prev = cur）。

不論哪種情況，cur 都往前一步 (cur = cur->next)。這裡的核心不變量 (invariant) 是：prev 永遠指向「已保證正確接好的鏈尾」，而 prev->next 到 cur 之間的重複段隨時可能被剪掉。走到底後回傳 dummy->next 即為答案。

English: The brute-force idea is to first count how many times each value occurs (say, with a hash map or a small counting array since values are only -100..100), then do a second pass deleting every node whose count exceeds one. That works but needs two passes and extra memory. But the list is already sorted, which means equal values are always grouped together (like 3,3 or 4,4,4). That lets us solve it in a single pass with no counting table.

The trick is two pointers plus a dummy node. Because even the head can be deleted, we create a dummy node with dummy->next = head so we never need a special case for removing the first node. prev starts at the dummy and always points to "the last node we've confirmed we're keeping, correctly linked." cur scans forward. At each step we compare cur->val with cur->next->val:

• Equal → we're at the start of a duplicate run. Advance cur forward until it passes the last node equal to that value, then splice the whole run out with prev->next = cur->next. Crucially, prev does not move, because the node now following prev hasn't been vetted yet.
• Different → cur is (so far) unique and safe to keep, so advance prev to cur.

In both cases cur then advances one step. The invariant is: prev always points at the tail of the verified-correct part of the list, and everything between prev->next and cur may still get cut. When we reach the end, dummy->next is the answer.

逐步走查 / Walkthrough

Input: head = [1,2,3,3,4,4,5]. 我們建立 dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5，prev = dummy，cur = 1。

We compare cur->val with cur->next->val each round.

Return dummy->next → [1,2,5]. ✅

小提醒：在 step 3，重複判斷是先用內層迴圈讓 cur 走到「這段重複的最後一個節點」，再做一次 splice；下面的程式碼會清楚呈現這個結構。 Note: in step 3 an inner loop first walks cur to the last node of the duplicate run, then one splice removes the whole run — the code below shows this structure clearly.

Solution — C

/*
 * 演算法 / Algorithm:
 * 串列已排序，重複值必相鄰。用 dummy 虛擬頭 + 雙指針單趟走訪。
 * The list is sorted, so duplicates are adjacent. Use a dummy head + two
 * pointers in one pass: prev = tail of verified-kept part, cur = scanner.
 * 遇到重複整段用 prev->next = cur->next 剪掉；否則 prev 前進。
 * Splice out an entire duplicate run; otherwise advance prev.
 */

// LeetCode 已定義好這個結構，這裡列出以便理解。
// LeetCode already defines this struct; shown here for clarity.
// struct ListNode { int val; struct ListNode *next; };

struct ListNode* deleteDuplicates(struct ListNode* head) {
    // 建立虛擬頭節點，放在真正 head 前面。
    // Create a dummy node placed before the real head.
    // 這樣即使第一個節點要被刪，也不用寫特例。
    // This avoids a special case when the first node must be deleted.
    struct ListNode dummy;          // 在堆疊上配置一個節點 / a node on the stack
    dummy.next = head;              // dummy 的 next 指向原本的 head / point dummy at head

    // prev：已確認保留、串接正確的最後一個節點，起點是 dummy。
    // prev: last confirmed-kept node (correctly linked); starts at dummy.
    struct ListNode* prev = &dummy; // &dummy 取 dummy 的位址 / address-of dummy

    // cur：向前探查的指標，從真正的 head 開始。
    // cur: the scanning pointer, starting at the real head.
    struct ListNode* cur = head;

    // 只要 cur 存在且有下一個節點可比較，就繼續。
    // Continue while cur exists and has a next node to compare against.
    while (cur != NULL && cur->next != NULL) {

        // 比較目前節點與下一個節點的值是否相同（重複的起點）。
        // Check if current value equals the next value (start of a duplicate run).
        if (cur->val == cur->next->val) {

            // 記住這個重複的值，等一下用它判斷該跳過哪些節點。
            // Remember this duplicated value to know which nodes to skip.
            int dupVal = cur->val;

            // 內層迴圈：讓 cur 一路前進，跳過所有等於 dupVal 的節點。
            // Inner loop: advance cur past every node equal to dupVal.
            while (cur != NULL && cur->val == dupVal) {
                struct ListNode* toFree = cur; // 先存起來以便釋放 / save to free it
                cur = cur->next;               // cur 走到下一個 / move cur forward
                free(toFree);                  // 歸還已刪節點的記憶體 / free removed node
            }

            // 把 prev 直接接到重複段之後，等於剪掉整段。
            // Link prev straight past the run, cutting the whole run out.
            // 注意：prev 不移動，因為新的 prev->next 還沒被驗證過。
            // Note: prev does NOT move; the new prev->next isn't vetted yet.
            prev->next = cur;

        } else {
            // 值不同 → cur 目前看來是唯一的，安全保留。
            // Values differ → cur is unique so far, safe to keep.
            prev = cur;        // prev 前進到 cur / advance prev to cur
            cur = cur->next;   // cur 前進一步 / advance cur one step
        }
    }

    // 回傳真正的頭節點（dummy 後面的那個）。
    // Return the real head (the node after dummy).
    return dummy.next;
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 排序串列中重複值相鄰。使用 dummy 虛擬頭 + 雙指針，一趟走訪即可。
 * In a sorted list duplicates are adjacent. Use a dummy head + two pointers
 * in a single pass. prev = tail of the kept part; cur scans forward and
 * whole duplicate runs are spliced out with prev->next = cur->next.
 */

// LeetCode 已提供 ListNode 定義 / LeetCode provides the ListNode definition:
// struct ListNode { int val; ListNode *next; ListNode(int x):val(x),next(nullptr){} };

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 虛擬頭節點：用 new 在堆積上建立，val 隨意（此處用 0）。
        // Dummy head: allocate with `new`; its value is irrelevant (0 here).
        // 目的是統一處理「連 head 都可能被刪」的情況。
        // Purpose: uniformly handle the case where the head itself is removed.
        ListNode* dummy = new ListNode(0);
        dummy->next = head;                 // dummy 接到原 head / link dummy to head

        // prev 指向已確認保留的最後一個節點，初始為 dummy。
        // prev points to the last confirmed-kept node; initially the dummy.
        ListNode* prev = dummy;

        // cur 是向前掃描的指標，從 head 開始。
        // cur is the forward scanner, starting at head.
        ListNode* cur = head;

        // 需要 cur 和 cur->next 都存在才能比較。
        // We need both cur and cur->next to exist to compare.
        while (cur != nullptr && cur->next != nullptr) {

            // 目前值等於下一個值 → 遇到重複區段。
            // Current value equals next value → a duplicate run begins.
            if (cur->val == cur->next->val) {

                int dupVal = cur->val;      // 記住重複的值 / remember the duplicated value

                // 內層迴圈：跳過所有等於 dupVal 的節點，順便釋放記憶體。
                // Inner loop: skip all nodes equal to dupVal, freeing them.
                while (cur != nullptr && cur->val == dupVal) {
                    ListNode* toDelete = cur; // 暫存要刪的節點 / hold node to delete
                    cur = cur->next;          // cur 前進 / advance cur
                    delete toDelete;          // 釋放記憶體，避免洩漏 / free to avoid leak
                }

                // 把整段重複剪掉；prev 不移動。
                // Splice the whole run out; prev stays put.
                prev->next = cur;

            } else {
                // 值不同 → 保留 cur，prev 前進。
                // Values differ → keep cur, advance prev.
                prev = cur;         // prev 移到 cur / move prev to cur
                cur = cur->next;    // cur 前進一步 / move cur forward
            }
        }

        // 暫存真正的答案頭節點，再把 dummy 釋放掉。
        // Save the real result head, then free the dummy node.
        ListNode* result = dummy->next;
        delete dummy;               // 釋放虛擬頭 / free the dummy
        return result;              // 回傳結果 / return the answer
    }
};

複雜度 / Complexity

• Time: O(n) — 每個節點只被 cur 走過一次（無論它是保留還是被刪除），沒有巢狀重走。n 是原串列的節點數。 / Each node is visited exactly once by cur, whether kept or deleted; the inner loop advances the same cur, so it never re-scans. n is the number of nodes.
• Space: O(1) — 只用了 dummy 和兩個指標，額外空間是常數，與 n 無關（原地修改）。 / Only a dummy node and two pointers are used — constant extra space, independent of n (in-place).

Pitfalls & Edge Cases

• 誤解題意：刪光 vs 留一個 / "delete all" vs "keep one". 本題（82）要把重複的全部刪除；很多人和第 83 題（每個值留一個）搞混。程式碼靠「值相同就跳過整段並用 prev->next = cur->next 剪掉」來確保一個不留。 / Problem 82 removes every copy of a duplicated value, unlike #83 which keeps one. The splice logic ensures none remain.
• prev 何時不能移動 / when NOT to move prev. 剪掉重複段後 prev 必須留在原地，因為新接上的 prev->next 還沒被檢查，可能又是重複值（例如 [1,1,2,2]）。若錯誤地移動 prev，就會漏刪。 / After splicing, prev must stay because its new next is unvetted and could also be a duplicate (e.g. [1,1,2,2]). Moving it wrongly leaks duplicates through.
• 空串列與單節點 / empty or single-node list. head 可能是 NULL/nullptr（0 個節點）。迴圈條件 cur != NULL && cur->next != NULL 會直接不進入，安全回傳 dummy.next（即原 head）。 / With 0 or 1 node the loop body never runs; dummy->next is returned correctly.
• 需要虛擬頭 / need the dummy. 若第一段就是重複（如 [1,1,1,2,3]），真正的 head 會被刪。沒有 dummy 就得為此寫特例；有了 dummy，prev 從 dummy 出發自然處理。 / When the leading value repeats ([1,1,1,2,3]), the head is deleted; the dummy removes the need for a special case.
• 懸空指標 / dangling pointer (C/C++). 在 free/delete 之前，一定要先用 cur = cur->next 取得下一個位址，否則釋放後再讀 cur->next 是未定義行為。程式碼用 toFree/toDelete 暫存後才釋放。 / Always read cur->next before freeing the node; the code caches the node in a temp and advances first to avoid use-after-free.
• 回傳值 / return value. 記得回傳 dummy->next，不是 head —— 原 head 可能已被刪除且指向已釋放記憶體。 / Return dummy->next, not the original head, which may have been deleted.