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