[LeetCode] Copy List with Random Pointer

https://oj.leetcode.com/problems/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.

Analysis

Apparently, it’s not a difficult question to clone a linked list without an additional random pointer. For us, the trickier part, however, is to clone the random list node structure. My idea is using a HashTable.

Code

/**
 * Author : Acjx
 * Email  : zhoujx0219@163.com
 */

/**
 * 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:
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    RandomListNode *copyRandomList(RandomListNode *head) 
    {
        RandomListNode *dummyHead = new RandomListNode(0);
        RandomListNode *p = head, *q = dummyHead;
        unordered_map<RandomListNode *, RandomListNode *> map;
        
        while (p != NULL)
        {
            q->next = new RandomListNode(p->label);
            map.insert(make_pair(p, q->next));
            p = p->next;
            q = q->next;
        }
        
        p = head; q = dummyHead;
        while (p != NULL)
        {
            q->next->random = map[p->random];
            p = p->next;
            q = q->next;
        }
        
        return dummyHead->next;
    }
};