问题

拷贝复杂链表。复杂链表的每个节点除了有next指针域，还有random指针域（指向任意节点或者NULL）。节点值可能重复。

算法：哈希

这道题的难点在于random指针域的拷贝。因为节点值可能重复，所以不能参考原链表的random指针指向的节点值，而是要看random指针指向的节点地址，这个地址是唯一的。

找到了唯一的标识，就可以用哈希表来做寻找了。

因此我们可以用哈希表来存储源节点-拷贝节点之间的映射：
1. 遍历原链表，对于每一个节点，拷贝分为创建和指向两步：
2. 创建工作：如果哈希表中没有对应的拷贝节点，则创建并记录哈希表；如果哈希表中没有源random节点对应的拷贝random节点，则创建并记录哈希表
3. 指向工作：将拷贝链表的尾部指向拷贝节点，同时将拷贝节点的random域指向拷贝random节点

复杂度

时间：$O(N)$
空间：$O(N)$

代码

一次遍历: 一边遍历一边建立哈希

/*
// 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) {
        Node *dummy = new Node(-1);
        Node *tail = dummy;
        unordered_map<Node*, Node*> hash;
        hash[nullptr] = nullptr;
        while(head){
            if(!hash.count(head)) hash[head] = new Node(head->val);
            if(!hash.count(head->random)) hash[head->random] = new Node(head->random->val);
            tail->next = hash[head];
            tail->next->random = hash[head->random];
            // cout<<tail->next->val<<endl;

            head = head->next;
            tail = tail->next;
        }

        return dummy->next;
    }
};

两次遍历，先建立好哈希，再填写指针引用

/*
// 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*> hash;
        Node* newhd;
        if(head == NULL) return NULL;
        for(Node* p = head; p != NULL; p = p->next){
            if(p == head){
                newhd = new Node(p->val);
                hash[p] = newhd;
            }
            else{
                hash[p] = new Node(p->val);
            } 
        }
        for(Node *p1 = head, *p2 = newhd; p1 != NULL; p1 = p1->next, p2 = p2->next){
            if(p1->next) p2->next = hash[p1->next];
            else p2->next = NULL;
            if(p1->random) p2->random = hash[p1->random];
            else p2->random = NULL;
        }
        return newhd;
    }
};