Copy List

• Time : $O(n)$
• Space : $O(n)$

/**
 * Definition for singly-linked list.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
RandomListNode* Solution::copyRandomList(RandomListNode* A) {
    unordered_map<RandomListNode*, RandomListNode*> mp;
    RandomListNode* runner = A;
    while(runner) {
        RandomListNode* copy = new RandomListNode(runner->label);
        mp[runner] = copy;
        runner = runner->next;
    }
    runner = A;
    while(runner) {
        mp[runner]->random = mp[runner->random];
        mp[runner]->next = mp[runner->next];
        runner = runner->next;
    }
    return mp[A];
}