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.

Solutin: Using hash map

We use dfs with a visited hash table to keep copying.

    RandomListNode *copyRandomListUtil(unordered_map<RandomListNode *, RandomListNode *> &copiedList, RandomListNode *head) {
        if(!head) return head;

        if(!copiedList[head]) {
            RandomListNode *newNode = new RandomListNode(head->label);
            copiedList[head] = newNode;
            newNode->next = copyRandomListUtil(copiedList, head->next);
            newNode->random = copyRandomListUtil(copiedList, head->random);
            return newNode;
        } else {
            return copiedList[head];
        }
    }

    RandomListNode *copyRandomList(RandomListNode *head) {
        unordered_map<RandomListNode *, RandomListNode *> copiedList;
        return copyRandomListUtil(copiedList, head);
    }