Solution using two hashmaps


#1

RandomListNode* Solution::copyRandomList(RandomListNode* head) {

    RandomListNode* ptr = head, *l1 = NULL, *temp = NULL;
    unordered_map<RandomListNode*, int>head_map;
    unordered_map<int, RandomListNode*>copy_map;
    int index = 0;
    
    while(ptr != NULL) {
        if(l1 == NULL) {
            l1 = new RandomListNode(ptr -> label);
            temp = l1;
        } else {
            temp -> next = new RandomListNode(ptr -> label);
            temp = temp -> next;
        }
        
        head_map[ptr] = index;
        copy_map[index] = temp;
        index++;
        ptr = ptr -> next;
    }
    
    ptr = head;
    
    while(ptr != NULL) {
        int index1 = head_map[ptr];
        int index2 = -1;
        
        if(head_map.find(ptr -> random) != head_map.end()) {
            index2 = head_map[ptr -> random];
        }
        
        copy_map[index1] -> random = index2 == -1 ? NULL : copy_map[index2];
        ptr = ptr -> next;
    }
    
    delete ptr;
    
    return l1;

}