Simplest C++ solution in O(n) time and O(1) extra space.


  • 0
    R
    /**
     * Definition for singly-linked list with a random pointer.
     * struct RandomListNode {
     *     int label;
     *     RandomListNode *next, *random;
     *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
     * };
     */
    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            
            RandomListNode *p=head, *temp=NULL, *r=NULL, *copy=NULL;
            
            if(!head)
                return NULL;
            
          
            
            while(p)         //making alternating new nodes in b/w
            {
                temp = new RandomListNode(p->label);
                temp->next = p->next;
                p->next = temp;
                p = p->next->next;
            }
         
            p=head, r=head->next;
            
            while(p && r && p->next)   //copying the randoms pointers of the orig list
            {
                if(p->random)
                    r->random = p->random->next;
             //   if(p->next)
                    p=p->next->next;
                if(r->next)
                    r=r->next->next;
            }
            
            p=head, r=head->next , copy=head->next;
            
            while(p && r && r->next)  // breaking the list into orig and new one.
            {
                p->next = p->next->next;
                r->next = r->next->next;
                p=p->next;
                r=r->next;
            }
            p->next=NULL;
            r->next=NULL;
            return copy;
        }
    };
    

Log in to reply
 

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