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

Example 1:

``````Input:
{"\$id":"1","next":{"\$id":"2","next":null,"random":{"\$ref":"2"},"val":2},"random":{"\$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.
``````

Note:

1. You must return the copy of the given head as a reference to the cloned list.

``````class Solution {
public:
Node *res = new Node(head->val, nullptr, nullptr);
Node *node = res, *cur = head->next;
unordered_map<Node*, Node*> m;
while (cur) {
Node *t = new Node(cur->val, nullptr, nullptr);
node->next = t;
m[cur] = t;
node = node->next;
cur = cur->next;
}
node = res; cur = head;
while (cur) {
node->random = m[cur->random];
node = node->next;
cur = cur->next;
}
return res;
}
};
``````

``````class Solution {
public:
unordered_map<Node*, Node*> m;
}
Node* helper(Node* node, unordered_map<Node*, Node*>& m) {
if (!node) return nullptr;
if (m.count(node)) return m[node];
Node *res = new Node(node->val, nullptr, nullptr);
m[node] = res;
res->next = helper(node->next, m);
res->random = helper(node->random, m);
return res;
}
};
``````

1. 在原链表的每个节点后面拷贝出一个新的节点。

2. 依次给新的节点的随机指针赋值，而且这个赋值非常容易 cur->next->random = cur->random->next。

3. 断开链表可得到深度拷贝后的新链表。

cur->next->random = cur->random->next;

``````class Solution {
public:
while (cur) {
Node *t = new Node(cur->val, nullptr, nullptr);
t->next = cur->next;
cur->next = t;
cur = t->next;
}
while (cur) {
if (cur->random) cur->next->random = cur->random->next;
cur = cur->next->next;
}
while (cur) {
Node *t = cur->next;
cur->next = t->next;
if (t->next) t->next = t->next->next;
cur = cur->next;
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/138

Clone Graph

https://leetcode.com/problems/copy-list-with-random-pointer/

https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43488/Java-O(n)-solution

https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43567/C%2B%2B-simple-recursive-solution

https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43491/A-solution-with-constant-space-complexity-O(1)-and-linear-time-complexity-O(N)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation