/**
 * 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) 
    {
        //insert copy
        if(head==NULL) return NULL;
        RandomListNode* p=head;
        while(p!=NULL)
        {
            RandomListNode* pnext=p->next;
            RandomListNode* pnew=new RandomListNode(p->label);
            p->next=pnew;
            pnew->next=pnext;
            p=pnext;
        }
        //the pointer
        RandomListNode* p1=head;
        RandomListNode* p2=head->next;
        while(true)
        {
            if(p1->random!=NULL) p2->random=p1->random->next;
            p1=p1->next->next;
            if(p1==NULL) break;
            p2=p2->next->next;
        }
        //split the 2 list
        RandomListNode* phead=head->next;
        p1=head;
        p2=phead;
        while(true)
        {
            RandomListNode* p1next=p1->next->next;
            p1->next=p1next;
            if(p1next==NULL) break;
            p2->next=p1next->next;
            
            p1=p1next;
            p2=p1next->next;
        }
        return phead;
    }
};