/*
 * 演算法 / 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
    }
};