剑指 Offer 35. 复杂链表的复制

题目：

/*
// 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) {
        if(head==NULL) return NULL;
        Node* cur=head;
        unordered_map<Node*,Node*> map;           //本题首先想到用unordered_map建立映射关系来复制和重构链表
        while(cur){
            map[cur]=new Node(cur->val);          //建立每一个节点的映射，map[cur]是键，new Node(cur->val)是对应的值
            cur=cur->next;
        }
        cur=head;
        while(cur){
            map[cur]->next=map[cur->next];         //重构新链表next指向
            map[cur]->random=map[cur->random];     //重构新链表random指向
            cur=cur->next;
        }
        return map[head];
    }
};

以上代码方法转自力扣评论区