Copy List with Random Pointer

LeetCode #138

Description:

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example:

/**
 * 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) {}
 * };
 */

Idea:

if(curr->random!=NULL){
    curr->next->random=curr->random->next;
}

Code:

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *curr;
        // create new nodes, and link the new nodes after the original nodes
        for(curr=head; curr!=NULL; curr=curr->next->next){
            RandomListNode *new_node=new RandomListNode(curr->label);
            new_node->next=curr->next;
            curr->next=new_node;
        }

        // make random pointer point to the correct location
        for(curr=head; curr!=NULL; curr=curr->next->next){
            if(curr->random!=NULL){
                curr->next->random=curr->random->next;
            }
        }

        // separate two linked list
        RandomListNode dummy_head(-1);
        RandomListNode * new_head = &dummy_head;
        curr=head;
        while(curr!=NULL){
            new_head->next=curr->next;
            new_head=new_head->next;
            curr->next=new_head->next;
            curr=curr->next;
        }

        return dummy_head.next;
    }
};