# 138-Copy List with Random Pointer
###### tags: `Medium`
## Question
https://leetcode.com/problems/copy-list-with-random-pointer/
## Key
- 如何複製list
## Reference
https://ithelp.ithome.com.tw/articles/10268463
## Solution
### Best sol.

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(nullptr==head){
            return head;
        }
        
        Node* cur = head;
        // create a new node for each node, and make the new node insert into the original nodes
        while(nullptr!=cur){
            Node* new_node = new Node(cur->val);
            new_node->next = cur->next;
            cur->next = new_node;
            cur = new_node->next;
        }
        
        // for the new nodes, make the random points to the new nodes
        cur = head;
        while(nullptr!=cur){
            if(nullptr!=cur->random)
            {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
        
        // separate the original list and the new list
        cur = head;
        Node* new_head=cur->next;
        Node* tmp= cur->next;
        while(nullptr!=cur){
            cur->next = cur->next->next;
            // the last tmp->next will be nullptr
            if(nullptr!=tmp->next){
                tmp->next = tmp->next->next;
            }
            cur = cur->next;
            tmp = tmp->next;
        }

        return new_head;
    }
};

### Hash table sol.

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> m;
        Node* ptr = head;
        while (ptr) {
            m[ptr] =new Node(ptr->val);
            ptr = ptr->next;
        }
        ptr = head;
        while (ptr) {
            m[ptr]->next = m[ptr->next];
            m[ptr]->random = m[ptr->random];
            ptr = ptr->next;
        }
        return m[head];
    }
};