138. 随机链表的复制
一句话套路原地把 next 指向克隆结点,再拆两条链
题目描述
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:
val:一个表示Node.val的整数。random_index:随机指针指向的节点索引(范围从0到n-1);如果不指向任何节点,则为null。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2:

输入:head = [[1,1],[2,1]] 输出:[[1,1],[2,1]]
示例 3:

输入:head = [[3,null],[3,0],[3,null]] 输出:[[3,null],[3,0],[3,null]]
提示:
0 <= n <= 1000-104 <= Node.val <= 104Node.random为null或指向链表中的节点。
思路
时间
O(n)空间
O(n)解法一(本文件采用)
两趟 + 哈希表 old->new。好懂、好讲。
解法二 O(1) 空间
先把 copy 插在 原结点 后面 A->A'->B->B',则 A'->random = A->random->next;最后再拆链。
图解
链表结构(来自本仓库测试数据)
C++17 题解
namespace lc0138 {
class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map<Node*, Node*> mp;
for (Node* p = head; p; p = p->next) mp[p] = new Node(p->val); // 只复制值
for (Node* p = head; p; p = p->next) {
mp[p]->next = p->next ? mp[p->next] : nullptr;
mp[p]->random = p->random ? mp[p->random] : nullptr; // 指针映射过去
}
return head ? mp[head] : nullptr;
}
};
// —— 测试脚手架:按下标数组构造随机链表 ——
inline Node* buildRandList(const vector<int>& vals, const vector<int>& randomIdx) {
vector<Node*> nodes;
for (size_t i = 0; i < vals.size(); ++i) nodes.push_back(new Node(vals[i]));
for (size_t i = 0; i < nodes.size(); ++i) {
if (i + 1 < nodes.size()) nodes[i]->next = nodes[i + 1];
nodes[i]->random = randomIdx[i] < 0 ? nullptr : nodes[randomIdx[i]];
}
return nodes.empty() ? nullptr : nodes[0];
}
inline vector<int> randRandomIdx(Node* head, const vector<Node*>& orig) {
vector<int> out;
for (Node* p = head; p; p = p->next) {
int idx = -1;
for (size_t i = 0; i < orig.size(); ++i)
if (orig[i] == p->random) idx = (int)i;
out.push_back(idx);
}
return out;
}
inline vector<Node*> collect(Node* head) {
vector<Node*> v;
for (Node* p = head; p; p = p->next) v.push_back(p);
return v;
}
// random 不影响 next 链,只顺着 next 释放即可(不会 double free)
inline void freeRandList(Node* head) {
while (head) {
Node* n = head->next;
delete head;
head = n;
}
}
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0138::Solution s;
Node* head = lc0138::buildRandList({7, 13, 11, 10, 1}, {-1, 0, 4, 2, 0});
Node* copy = s.copyRandomList(head);
CHECK_EQ(lc0138::collect(copy).size(), (size_t)5); // 长度一致
CHECK_EQ(lc0138::randRandomIdx(copy, lc0138::collect(copy)),
vector<int>{-1, 0, 4, 2, 0}); // random 相对结构一致
CHECK_TRUE(copy != head); // 必须是新结点
CHECK_TRUE(copy->next != head->next);
Node* empty = s.copyRandomList(nullptr);
CHECK_TRUE(empty == nullptr);
lc0138::freeRandList(head);
lc0138::freeRandList(copy);