/*
 * 雜湊表法 / Hash-map approach (O(n) time, O(n) space):
 *   Pass 1: 為每個舊節點造一個新節點，存進 unordered_map<舊, 新>。
 *           Create a copy per old node; remember old→new in a map.
 *   Pass 2: 用查表把新節點的 next 與 random 接好。
 *           Use the map to wire each copy's next and random.
 * 這個版本比原地交錯更好讀，很適合初學者理解問題本質。
 * Easier to read than interweaving — great for grasping the core idea.
 */

// LeetCode 已定義 class Node { int val; Node* next; Node* random; ... };
// LeetCode already provides the Node class.

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // unordered_map 是雜湊表，查找/插入平均 O(1)。鍵是舊節點指標，值是新節點指標。
        // unordered_map = hash table with average O(1) ops; key = old ptr, value = new ptr.
        unordered_map<Node*, Node*> map;

        // ---- Pass 1: 只複製值，建立對應關係 / copy values, build the mapping ----
        for (Node* cur = head; cur != nullptr; cur = cur->next)  // range 太麻煩，手動走串列 / manual walk
            map[cur] = new Node(cur->val);       // new 動態配置一個新節點 / new allocates one node

        // ---- Pass 2: 接好 next 與 random / wire next and random ----
        for (Node* cur = head; cur != nullptr; cur = cur->next) {
            // 小技巧：map[nullptr] 會回傳預設值 nullptr，所以尾端與空 random 自動處理正確。
            // Trick: map[nullptr] yields the default nullptr, so tail / null-random just work.
            map[cur]->next   = map[cur->next];   // 新節點的 next = 舊 next 對應的新節點 / copy's next
            map[cur]->random = map[cur->random]; // 新節點的 random = 舊 random 對應的新節點 / copy's random
        }

        return map[head];  // 回傳頭節點的副本；head 為 null 時 map[head] 也是 nullptr / head's copy
    }
};