這道題最直接的辦法，是two pass. 第一遍copy 不帶random pointer. 第二遍copy random pointer.
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if(!head) return NULL;
unordered_map<RandomListNode*, RandomListNode*> mp;
RandomListNode *head_copy = new RandomListNode(head->label);
mp[head] = head_copy;
RandomListNode *cur = head->next, *pre = head_copy;
while(cur){
RandomListNode *cur_copy = new RandomListNode(cur->label);
mp[cur] = cur_copy;
pre->next = cur_copy;
pre = cur_copy;
cur = cur->next;
}
cur = head;
while(cur){
RandomListNode *node = cur->random;
if(node){
mp[cur]->random = mp[node];
}
cur = cur->next;
}
return head_copy;
}
};
最近也才發(fā)現(xiàn)有神奇的one pass方法孤页，copy node的同時(shí)荧关，將random node也新建出來(lái)挡闰，放進(jìn)map里
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
if(!head) return NULL;
unordered_map<RandomListNode*, RandomListNode*> mp;
RandomListNode *dummy = new RandomListNode(0);
RandomListNode *cur = head, *pre = dummy;
while(cur){
RandomListNode *cur_copy = NULL;
if(mp.count(cur)){
cur_copy = mp[cur];
}else{
cur_copy = new RandomListNode(cur->label);
mp[cur] = cur_copy;
}
RandomListNode *random = cur->random;
if(random != NULL){
if(mp.count(random)){
cur_copy->random = mp[random];
}else{
RandomListNode *random_copy = new RandomListNode(random->label);
mp[random] = random_copy;
cur_copy->random = random_copy;
}
}
pre->next = cur_copy;
pre = cur_copy;
cur = cur->next;
}
RandomListNode *ret = dummy->next;
delete dummy;
return ret;
}
};
