Getting MLE using hasmap approach


#1
RandomListNode* Solution::copyRandomList(RandomListNode* A) {

    RandomListNode* head=A;
    unordered_map<RandomListNode*,RandomListNode* >m;
    int i=1;
    
    while(A!=NULL)
    {
        
        if(m.find(A)==m.end())
        {RandomListNode *a = new RandomListNode(A->label);
        m.insert(make_pair(A,a));}
        i++;
        A=A->next;
    }
    A = head;
    while(A!=NULL)
    {
        m[A]->label= A->label;
        if(A->next!=NULL)
        m[A]->next = m[A->next];
        if(A->random!=NULL)
        m[A]->random = m[A->random];
        A = A->next;
    } 
    
return m[head];
}

#2

My solution works after using two hashmaps. I have used key as index of the node which is less costly than using node as a key

    /**
  • 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) {

     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;
    

}