Copy List with Random Pointer

Copy List with Random Pointer

 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.

----------------------------- thinking ------------------------------
method 1: using hash table to record the corresponding relationship between original list and new copy
method 2: using interleaving original list and new copy to record the relationship, and then split them into two parts

----------------------------- codes ---------------------------------
/**
 * 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;
        RandomListNode *next = cur;
        // create new node and interleave it with the original list
        while (cur) {
            next = cur->next;
            RandomListNode *ele = new RandomListNode(cur->label);
            cur->next = ele;
            ele->next = next;
            cur = next;
        }
        // assign the right random list to the new created nodes
        cur = head;
        while (cur) {
            next = cur->next->next;
            if (cur->random) {
                cur->next->random = cur->random->next;
            } else {
                cur->next->random = NULL;
            }
            cur = next;
        }
        // split the list and get the new copy
        RandomListNode dummy1(0);
        RandomListNode dummy2(0);
        RandomListNode *par1 = &dummy1;
        RandomListNode *par2 = &dummy2;
        cur = head;
        while (cur) {
            next = cur->next->next;
            par1->next = cur;
            par2->next = cur->next;
            par1 = par1->next;
            par2 = par2->next;
            par1->next = NULL;
            par2->next = NULL;
            cur = next;
        }
        return dummy2.next;
    }
};