Copy List with Random Pointer

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

/**

 * Definition for singly-linked list with a random pointer.

 * struct RandomListNode {

 *     int label;

 *     RandomListNode *next, *random;

 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}

 * };

 */

Solution: The trick part is that when you try to link the random pointer to a node, it may not exist yet.  So the solution has to generate all nodes first, then make connection.

In the first pass (of the link list), we copy all nodes and map the old nodes to new nodes. 

In the second pass (of the map), we copy the way of the connections if they are not nullptr;

#include <unordered_map>
using namespace std;

class RLN{

public:

        RandomListNode *copyRandomList(RandomListNode *head) {
        unordered_map<RandomListNode*,RandomListNode*> mymap;
        //copy link list without random; and put to map<old, new>
        if (!head) return nullptr;
        RandomListNode* cur=head;
        while(cur){
            RandomListNode* temp=new RandomListNode(cur->label);
            mymap.emplace(cur,temp);
            cur=cur->next;
        }
        for (auto &ele:mymap){
            if (ele.first->next!=nullptr) {
                ele.second->next= mymap[ele.first->next];
            }
            if (ele.first->random!=nullptr) {
                ele.second->random= mymap[ele.first->random];
            }
        }
        return mymap[head];
    }

};