CPP HashMap One Pass Solution


  • 0

    I think when we use hashmap to record the address of the node, it doesn't necessary to pass the list twice. One pass is enough!

     RandomListNode *copyRandomList(RandomListNode *head) {
              if(head==NULL) return NULL;
              RandomListNode *cur=head;
             
              while(cur!=NULL){
                  if(!hashmap.count(cur))
                     hashmap[cur]=new RandomListNode(cur->label);
                     
                  RandomListNode *nextnode=cur->next;
                  if(nextnode!=NULL){
                      if(!hashmap.count(nextnode)){
                          RandomListNode *newnext=new RandomListNode(nextnode->label);
                          hashmap[nextnode]=newnext;
                      }
                      hashmap[cur]->next=hashmap[nextnode];
                  }
                  
                  RandomListNode *rnode=cur->random;
                  if(rnode!=NULL){
                      if(!hashmap.count(rnode)){
                          RandomListNode *newrandom=new RandomListNode(rnode->label);
                          hashmap[rnode]=newrandom;
                      }
                      hashmap[cur]->random=hashmap[rnode];
                  }
                  cur=cur->next;
              }
              return hashmap[head];
         }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.