My three steps CPP solution, easy to understand


  • 0
    W
    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
          if(head==nullptr)
          return head;
          
          //in place copy
          RandomListNode* temp;
          RandomListNode* temp_head=head;
          while(temp_head!=nullptr){
              temp=temp_head->next;
              RandomListNode* newNode=new RandomListNode(temp_head->label);
              newNode->next=temp;
              temp_head->next=newNode;
              temp_head=temp;
          }
          
          
          //copy random pointer
          temp_head=head;
          while(temp_head!=nullptr){
              if(temp_head->random!=nullptr)
               temp_head->next->random=temp_head->random->next;
              else
               temp_head->next->random=nullptr;
              temp_head=temp_head->next->next;
          }
          
          
          //split the odd and even nodes
          RandomListNode* headOfNew=head->next;
          RandomListNode* odd=head;
          RandomListNode* even=head->next;
          while(even->next!=nullptr){
              temp=odd->next->next;
              odd->next=temp;
              
              temp=even->next->next;
              even->next=temp;
              
              odd=odd->next;
              even=even->next;
          }
          
          odd->next=nullptr;//add this, do not forget!!!!!!!!!
         
          //finally return  new randomlist
          return headOfNew;
          
          
        }
    };

Log in to reply
 

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