[recommend for beginners]clean C++ implementation with detailed explaination


  • 3

    At the first glance, I want to use the extra linked-list to solve it.

    For example

     A->B->C->NULL     
    
     A->random=C     
    
     B->random=A    
    
     C->random=A
    
     a->b->c->NULL       
    

    I will set the

     A->next=a    
    
     a->random=A    
    

    then I have

     a->random=a->random->random->next
    

    But I have make the original-linked-list messy. So I need to restore the original linked list. I just need to

    change from

           "A->next=a"  to "A->next=B" 
    

    TO DO THIS !

    I have to copy the original-next-linked-list for another copy I mean like

        aa->bb->cc->NULL   
    
        with  aa->random=A   
    
         bb->random=B  
    
         cc->random=C
    

    So, at last we need to set

        "aa->random->next=aa->next->random"
    

    So we get the final solution. ALL IN ALL, we have to copy the original-linked-list for 2 copies to recover

    the original-linked-list.

    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            if(!head)   return NULL;
            
            //create the insert-mixed-linked-list
            RandomListNode *cur=head;
            while(cur){
                RandomListNode *nextPtr=cur->next;
                RandomListNode *temp=new RandomListNode(cur->label);
                cur->next = temp;
                temp->next=nextPtr;
                cur=nextPtr;
            }
            
            //assign the random-pointer-of-the-inserted-node
            cur=head;
            while(cur){
                RandomListNode *nextPtr=cur->next->next;
                if(cur->random){
                    cur->next->random = cur->random->next;
                }
                cur=nextPtr;
            }
            
            //extract the original-linked-list and deep-copy-of-the-original-linked-list
            RandomListNode *dummy=new RandomListNode(-1), *copyCur=dummy;
            cur=head;
            while(cur){
                copyCur->next=cur->next;
                copyCur=cur->next;
                cur->next=cur->next->next;
                cur=cur->next;
            }
    
            return dummy->next;
        }
    };

  • 0

    The first step idea is important, it is to construct from

              1 -> 2 ->3->NULL
    

    TO

             1->11->2->22->3->33->NULL

  • 0

    I rewrite it by myself. Except the wrong caused by missing a ";".

    I also meet RE as I have not check cur->random is NULL ??

    So we should add

      if(cur->random)  
    

    to make the code robust.

    Here is the final code:

    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            RandomListNode* dummy=new RandomListNode(-1);
            
            if(!head)  return dummy->next;
            /** step 1 , insert copy list crossly **/
            RandomListNode* cur=head;
            while(cur){
                RandomListNode* temp=new RandomListNode(cur->label), *next=cur->next;
                cur->next=temp;
                temp->next=next;
                cur=next;
            }
            /** assign the random pointer **/
            cur=head;
            while(cur){
                RandomListNode* next=cur->next->next;
                /** the random field maybe NULL, so checking is necessary **/ 
                if(cur->random)
                    cur->next->random=cur->random->next;
                cur=next;
            }
            /** recover the list **/
            cur=head;
            RandomListNode *r_cur=dummy;
            /** there is a lit bit messy to recover the list **/
            while(cur){
                r_cur->next=cur->next;
                r_cur=cur->next;
                cur->next=cur->next->next;
                cur=cur->next;
            }
            return dummy->next;
        }
    };

  • 0
    2

    I made mistakes at the final step to seperate the 2 merged list .....

        RandomListNode copy_dummy(-1), *copy_cur = &copy_dummy;
        cur = head;
        while(cur) {
            copy_cur->next = cur->next;
            copy_cur = cur->next;
            
            cur->next = cur->next->next;
            cur = cur->next;
        }
        
        return copy_dummy.next;

Log in to reply
 

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