题目描述：长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点，构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点成，其中每个新节点的值都设为其对应的原节点的值，复制链表中的指针都不应指向原链表中的节点 。

难点：遍历无法构造random指针指向

方法1：使用哈希表，key->value,映射为原节点->新节点，第一次遍历单纯构建节点，不指定指针，第二次遍历指定指针

如果访问map[key]，key不存在，会返回value的默认值，比如value是对象，返回NULL

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return NULL;
        unordered_map<Node*,Node*>map;
        Node* p = head;
        while(p){
            map[p] = new Node(p->val);
            p = p->next;
        }
        p = head;
        while(p){
            map[p]->next = map[p->next];
            map[p]->random = map[p->random];
            p = p->next;
        }
        return map[head];
    }
};