/*
 * 原地交錯法 / In-place interweaving (O(1) extra space):
 *   1) 把每個新節點插在對應舊節點後面：A → A' → B → B' → …
 *      Splice each copy right after its original.
 *   2) 利用 cur->next 就是副本這點來接 random。
 *      Use "the copy sits at cur->next" to set random pointers.
 *   3) 把交錯串列拆回舊串列 + 新串列。 Unzip into two lists.
 */

// LeetCode 已定義 struct Node { int val; struct Node *next; struct Node *random; };
// LeetCode already provides the Node definition above the function.

struct Node* copyRandomList(struct Node* head) {
    if (head == NULL) return NULL;              // 空串列直接回傳 null / empty list → null

    // ---- Pass 1: 交錯插入副本 / interweave copies ----
    struct Node* cur = head;                    // cur 指向目前的舊節點 / current old node
    while (cur != NULL) {                        // 走遍每個舊節點 / visit every old node
        // malloc 向系統要一塊 Node 大小的記憶體 / malloc grabs memory for one Node
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;                    // 複製值 / copy the value
        copy->next = cur->next;                  // 副本接到 cur 原本的下一個 / copy points to cur's old next
        copy->random = NULL;                     // random 之後才設，先清空 / clear random for now
        cur->next = copy;                        // 把副本插在 cur 後面 / insert copy right after cur
        cur = copy->next;                        // 跳過副本，走到下一個舊節點 / skip copy → next old node
    }

    // ---- Pass 2: 設定 random / assign random pointers ----
    cur = head;                                  // 從頭再走一次 / restart from head
    while (cur != NULL) {                         // cur 一律停在舊節點上 / cur always on an old node
        if (cur->random != NULL)                 // 舊節點有 random 才需要處理 / only if random exists
            // cur->next 是 cur 的副本；cur->random->next 是目標的副本
            // cur->next is cur's copy; cur->random->next is the target's copy
            cur->next->random = cur->random->next;
        cur = cur->next->next;                    // 跳過副本，前進到下一個舊節點 / advance two steps
    }

    // ---- Pass 3: 拆開兩條串列 / separate the two lists ----
    cur = head;                                  // 再次從頭 / restart from head
    struct Node* newHead = head->next;           // 新串列的頭就是第一個副本 / new head = first copy
    while (cur != NULL) {                          // 逐一還原並抽出 / restore & extract node by node
        struct Node* copy = cur->next;           // copy 是 cur 的副本 / copy is cur's clone
        cur->next = copy->next;                   // 舊節點跳過副本，接回原本的下一個舊節點 / relink old list
        if (copy->next != NULL)                   // 若後面還有節點 / if a next old node exists
            copy->next = copy->next->next;        // 副本也跳過一個舊節點，接到下一個副本 / relink new list
        cur = cur->next;                          // 前進到下一個舊節點 / move to next old node
    }

    return newHead;                              // 回傳新串列的頭 / return head of the copy
}