[LeetCode] Copy List with Random Pointer

Problem Statement (link):

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.

Analysis:
A naive thought is to create a new linked list as we scan through the given list. As we need to separate adding next pointer and adding random pointer (random pointer may point to node that hasn't been constructed yet), the time complexity is O(n^2), dominates by adding random pointer where we need to scan n nodes - worst case - to add 1 node's random pointer.

The trick is to construct the new list nodes in the original list. Let's say we have the following three node list:

                                                                

Note: this image is from here. Courtesy of Lei Zhang.

This algorithm has three steps:
1) Insert new nodes to the original linked list, configure the next pointer of each node --> O(n)
2) Configure the random pointers of each node --> O(n)
3) Break the list --> O(n)

The overall time complexity of O(n).

Code:

/**
 * 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) {
        if (head==NULL) return NULL;
        RandomListNode* cur=head;
        // Insert, link next pointers - O(n)
        while(cur!=NULL) {
            RandomListNode* cur1=new RandomListNode(cur->label);
            cur1->next=cur->next;
            cur->next=cur1;
            cur=cur1->next;
        }

        // Relink the random pointers - O(n)
        cur=head;
        while(cur!=NULL) {
            if (cur->random!=NULL)
                cur->next->random=cur->random->next;
            cur=cur->next->next;
        }

        // Break list - O(n)
        RandomListNode* newHead=head->next;
        cur=head;
        while(cur!=NULL) {
            RandomListNode* cur1=cur->next;
            cur->next=cur1->next;
            if (cur1->next!=NULL)
                cur1->next=cur1->next->next;
            cur=cur->next;
        }
 
        return newHead;
    }
};