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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/138-copy-list-with-random-pointer.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.