hash, two pass, O(n)

class Solution {
public:
    Node* copyRandomList(Node* head) {
       unordered_map<Node*, Node*> hash;
       Node dummy(0);
       Node* tail = &dummy;
       Node* pre = head;

       //copy list without random pointer
       while(pre){
           tail->next = new Node(pre->val);
           hash[pre] = tail->next;
           //
           pre = pre->next;
           tail = tail->next; 
       }

       //copy the random pointer
       pre = head;
       while(pre){
           Node* node = hash[pre];
           Node*  next = hash[pre->random];
           node->random = next;
           pre = pre->next;
       }                 

       return dummy.next;
    }
};