2019-11-08 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

示例：

输入： {"id":"2","next":null,"random":{"ref":"2"},"val":1}

解释： 节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。

提示：

1. 你必须返回给定头的拷贝作为对克隆列表的引用。

C++1

使用两次遍历+hash表。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node *> nodemap;
        Node *temp = head;
        Node *new_head = new Node(0,NULL,NULL);
        Node *copy_temp = new_head;
        
        while(temp){
            copy_temp->next = new Node(temp->val,NULL,NULL);
            nodemap[temp] = copy_temp->next;
            
            temp = temp->next;
            copy_temp = copy_temp->next;
        }
        
        Node * random_temp = NULL;
        temp = head;
        copy_temp = new_head->next;
        
        while(temp){
            random_temp = temp->random;
            if(random_temp){
                copy_temp->random = nodemap[random_temp];
            }else{
                copy_temp->random = NULL;
            }
            temp = temp->next;
            copy_temp = copy_temp->next;
        }
        
        return new_head->next;
    }
};