138 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.

The Idea: First store all the elements into a hash table. Map the address of each pointer to a node copy. At this point, we have all the space allocated that is needed and the only remaining tasks are remapping the pointers to their correct locations. Iterating through the linked list again, we can access each element in the unordered_mapin order since we stored each original address.

Complexity: O(n) time and space

RandomListNode *copyRandomList(RandomListNode *head) {
    if (!head) return nullptr;

    unordered_map<RandomListNode*, RandomListNode*> rand_memory;
    RandomListNode *iter = head;

    while (iter) {
        rand_memory.insert({iter, new RandomListNode(iter->label) });
        iter = iter->next;
    }

    iter = head;
    while (iter) {
        rand_memory[iter]->next = rand_memory[iter->next];
        rand_memory[iter]->random = rand_memory[iter->random];
        iter = iter->next;
    }

    return rand_memory[head];
}