/**
 * 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) {
            return nullptr;
        }
        RandomListNode* curr = head;
        while (curr) {
            RandomListNode* replica = new RandomListNode(curr->label);
            replica->next = curr->next;
            curr->next = replica;
            curr = replica->next;
        }
        curr = head;
        while (curr) {
            if (curr->random) {
                curr->next->random = curr->random->next;
            }
            curr = curr->next->next;
        }
        RandomListNode dummy(-1);
        RandomListNode* res_head = &dummy;
        curr = head;
        while (curr) {
            res_head->next = curr->next;
            curr->next = curr->next->next;
            res_head = res_head->next;
            res_head->next = nullptr;
            curr = curr->next;
        }
        return dummy.next;
    }
};