Simple yet best solution in C++ using constant space


  • 2
    • clone each node of the list and connect the cloned just after its original
    • the random pointer of the cloned node can be easily fetched by its previous node p->random->next
    • split the original node and its cloned collecting the odd and even nodes in a list
    class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) 
        {
            RandomListNode newHead(0), *p = head, *t = NULL;
            while(p)
            {
                RandomListNode *cloned = new RandomListNode(p->label);
                cloned->next = p->next;
                p->next = cloned;
                p = cloned->next;
            }
            
            p = head;
            while(p && p->next)
            {
                if(p->random) p->next->random = p->random->next;
                p = p->next->next;
            }
            
            p = head;
            t = &newHead;
            while(p && p->next)
            {
                t->next = p->next;
                p->next = p->next->next;
                t = t->next;
                p = p->next;
            }
            t->next = NULL;
            return newHead.next;
        }
    };
    
    

  • 0
    F

    @LHearen
    9 line: cloned->next = next; should be cloned->next = p->next;. Maybe that's why you get a negative.


  • 0

    @xrfind Sorry about it, my bad...weird...I must have forgotten to up my source file after modifying it in the OJ. Thanks for your checking and feedback.


  • 0
    N

    sorry,i really can not understand the code under here:

    while(p && p->next)
    {
        if(p->random) p->next->random = p->random->next;
            p = p->next->next;
    }
    

    why did this operation,i am in confusion


  • 0

    @Nicksxs Each new cloned nodes are just next to its previous originals so do the random ones;

    • this operation is trying to connect to the randoms

    p is the original then p->next is the new cloned so the random of p is cloned and placed at p->random->next (since each new cloned are placed just after the original) so at last p->next->random should be p->random->next right?


  • 0
    N

    @LHearen
    last night i read this code again,find that i haven't understand code in the first while loop at first,think it's just copy the node's value and it's next point. now i catch the point how this code done,really awesome,thank you!


  • 0

    @Nicksxs Sure thing, man. Have fun!


Log in to reply
 

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