138. Copy List with Random Pointer

解題思路

要 deep copy 一個 linked list，而且該 linked list 有名為 random 的屬性，會隨機指到 list 中其他 node。

用 two pass 的方式解題，第一次單純把 node 與 val 弄好，第二次則根據對照把 random 補上去。

程式碼

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node *dummy = new Node(0);
        Node *newHead = dummy, *p = head;
        unordered_map<Node*, Node*> mp; // old, new

        while(p != nullptr)
        {
            newHead->next = new Node(p->val);
            newHead = newHead->next;
            mp[p] = newHead;
            p = p->next;
        }

        newHead = dummy->next, p = head;
        while(newHead != nullptr)
        {
            newHead->random = mp[p->random];
            newHead = newHead->next;
            p = p->next;
        }
        return dummy->next;
    }
};