Leetcode -- Copy List with Random Pointer

 
/**  
  * 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;  
     while(p != NULL) {  
        RandomListNode * newNode = new RandomListNode(0);  
    newNode->label = p->label;  
       newNode->next = p->next;  
       newNode->random = p->random;  
       p->next = newNode;  
       p = p->next->next;  
     }  
     p = head;  
     while(p != NULL) {  
       RandomListNode * nextNode = p->next;  
       if(nextNode->random != NULL) {  
         nextNode->random = nextNode->random->next;  
       }  
       p = p->next->next;  
     }  
     p = head;  
     RandomListNode * dummy = new RandomListNode(-1);  
     RandomListNode * q = dummy;  
     while(p != NULL) {  
       q->next = p->next;  
       q = q->next;  
       p->next = q->next;  
       q->next = NULL;  
       p = p->next;  
     }  
     return dummy->next;  
   }  
 };