> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/138-copy-list-with-random-pointer.md).

# 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_map`in order since we stored each original address.

**Complexity:** O(n) time and space

```cpp
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];
}
```