Simple solution and approach in C++


#1

The hard part of this question is to understand what you really have to do. Once you’ve done that, the next step is to decide what to use the hasmap for. We’ll use the hashmap to store the original node’s address as the key and it’s corresponding new address for the new list as the value so in the end we have a hashmap representing old and new address of a label as key value pairs. We can create an empty list while doing so and populate it later by setting the random pointer from the hashmap.

/**
 * Definition for singly-linked list.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
RandomListNode* Solution::copyRandomList(RandomListNode* head) {
    
    //create a hashmap to store current address and new address as key value pairs
    unordered_map<RandomListNode*,RandomListNode*> m;
    RandomListNode* temp, *newHead=NULL,*i=head;
    
    //traverse the original list and store the current node's 
    //address and new node's address
    
    while(i!=NULL){
        RandomListNode* n=new RandomListNode(0);
        
        //set new head, this will be the head that you will return at last
        if(newHead==NULL){
            newHead=n;
        }
        else{
            temp->next=n;
        }
    m[i]=n;
    temp=n;
    i=i->next;
    }
    
    //now travserse the list to set the label, next and 
    //random pointer of the new list
    
    i=head;
    temp=newHead;
    
    while(i!=NULL){
        temp->label=i->label;
        temp->random=m[i->random];
    temp=temp->next;
    i=i->next;
    }
    
    return newHead;
}