參考了這篇>https://leetcode.com/problems/copy-list-with-random-pointer/solutions/4003262/97-92-hash-table-linked-list/?envType=daily-question&envId=2023-09-05

hashmap具有索引性，用來對付pointer of random相當適合。此解法先將每個節點掛在hashmap，再重走一遍把該串的串起來，最後回傳head的點。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> umap;
        Node* curr = head; 

        while(curr){
            umap[curr] = new Node(curr->val);
            curr = curr->next;
        }

        curr = head;

        while(curr){
            umap[curr]->next = umap[curr->next];
            umap[curr]->random = umap[curr->random];
            curr = curr->next;
        }
        return umap[head];
    }
};