Why do we have to use Hashing at all?


#1

Why doesn’t this solution work?

    RandomListNode* Solution::copyRandomList(RandomListNode* A) {
    
    RandomListNode* temp, *temp2, *newHead=NULL, *i=A;
    
    while(i!=NULL){
        RandomListNode* n = new RandomListNode(i->label);
        temp2 = i->random;
        RandomListNode* n2 = new RandomListNode(temp2->label);
        if(newHead==NULL){
            newHead=n;
        }
        else{
            temp->next = n;
            temp->random = n2;
        }
        
        temp=n;
        i=i->next;
    }
    
    return newHead;
}

#2

This code creates separate Nodes for random pointers. It does not point to the Nodes of the main list instead it points to extra Nodes.