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

## Thoughts

深度copy每个结点带有随机指针的列表，随机指针可指向列表中任意结点。深copy都是先建立起新节点和旧结点的一一映射，然后再去完善它们内部关系。Random pointer有一种很巧妙的解法，就是把复制出来的节点放在原节点旁(next)一一串起来。再重头遍历，每个节点的cp节点的random就是原节点random的next。再重头遍历，把cp节点依次串起来。

## Code

```cpp
/*
 * @lc app=leetcode id=138 lang=cpp
 *
 * [138] Copy List with Random Pointer
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        auto cur = head;
        while (cur != nullptr) {
            auto node = new Node(cur->val, cur->next, nullptr);
            cur->next = node;
            cur = node->next;
        } 
        cur = head;
        while (cur != nullptr) {
            auto node = cur->next;
            if (cur->random != nullptr) node->random = cur->random->next;
            cur = node->next;
        }
        auto new_head = head->next, new_cur = new_head;
        cur = head;
        while (cur != nullptr) {
            cur->next = new_cur->next;
            cur = cur->next;
            if (cur != nullptr) {
                new_cur->next = cur->next;
                new_cur = new_cur->next;
            }
        }
        return new_head;
    }
};
// @lc code=end


```

```cpp
/*
 * @lc app=leetcode id=138 lang=cpp
 *
 * [138] Copy List with Random Pointer
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        unordered_map<Node*, Node*> m;
        auto cur = head;
        while (cur != nullptr) {
            m[cur] = new Node(cur->val, nullptr, nullptr);
            cur = cur->next;
        } 
        cur = head;
        while (cur != nullptr) {
            m[cur]->random = m[cur->random];
            m[cur]->next = m[cur->next];
            cur = cur->next;
        }
        return m[head];
    }
};
// @lc code=end


```

## Analysis

TC: O(n), SC: O(n)

还有SC O(1)的解法：

把每个复制出来的结点和原结点紧挨着放在一个list里，这样找到原结点的random就能定位到新结点的random。


---

# 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://hao-fu-1.gitbook.io/oj/linked_list/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.