方法一:递归
unordered_map<Node*,Node*> dict;
Node* copyRandomList(Node* head) {
if (!head) return head;
if (dict.count(head)) return dict[head];
dict[head]=new Node(head->val, nullptr, nullptr);
dict[head]->next=copyRandomList(head->next);
dict[head]->random=copyRandomList(head->random);
return dict[head];
}
方法二:非递归
Node* copyRandomList(Node* head)
{
if (!head) return head;
unordered_map<Node*,Node*> m;
Node *p=head;
while(p) // make a copy of nodes
{
m[p]=new Node(p->val,nullptr,nullptr);
p=p->next;
}
p=head;
while(p) // link everyone and fill the random field
{
m[p]->next=m[p->next];
m[p]->random=m[p->random];
p=p->next;
}
return m[head];
}