Copy List with Random Pointer (Leetcode 138, Lintcode 105)

这道题最直接的办法，是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;
    }
};

最近也才发现有神奇的one pass方法，copy node的同时，将random node也新建出来，放进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;
    }
};