0138. Copy List with Random Pointer¶
题目信息¶
- 题号:
复制带随机指针的链表
- 难度:
Medium
- 主题:
链表、深拷贝、节点映射、原地穿插
- 原题:
- 重点:
先保证每个原节点有唯一副本,再复制两类引用;用相邻位置编码映射并在拆分时恢复原链
题目重述¶
链表节点包含 val、next 和 random。next 指向下一个节点,random 可以指向链表内任意
节点或为空。返回整条结构的深拷贝:每个原节点都对应一个全新副本,副本间的 next、random 关系
与原结构相同,返回结构中不能留下任何原节点引用。空链表返回 nullptr。
自建示例¶
next: A(4) -> B(4) -> C(9) -> null
random: A -> C,B -> A,C -> C
副本应为 a -> b -> c,其中 a.random = c、b.random = a、c.random = c。A 与 B
值相同,仍是两个不同对象,必须创建两个不同副本。若某节点 random = null,对应副本也应指向空。
C++ 实现¶
#include <unordered_map>
class Solution {
private:
Node* copyWithAddressMap(Node* head) {
if (head == nullptr) {
return nullptr;
}
std::unordered_map<Node*, Node*> copies;
for (Node* original = head;
original != nullptr;
original = original->next) {
copies[original] = new Node(original->val);
}
for (Node* original = head;
original != nullptr;
original = original->next) {
Node* copy = copies[original];
copy->next = original->next == nullptr
? nullptr
: copies[original->next];
copy->random = original->random == nullptr
? nullptr
: copies[original->random];
}
return copies[head];
}
Node* copyByInterleaving(Node* head) {
if (head == nullptr) {
return nullptr;
}
for (Node* original = head; original != nullptr;) {
Node* nextOriginal = original->next;
Node* copy = new Node(original->val);
original->next = copy;
copy->next = nextOriginal;
original = nextOriginal;
}
for (Node* original = head; original != nullptr;) {
Node* copy = original->next;
copy->random = original->random == nullptr
? nullptr
: original->random->next;
original = copy->next;
}
Node* copyHead = head->next;
for (Node* original = head; original != nullptr;) {
Node* copy = original->next;
Node* nextOriginal = copy->next;
original->next = nextOriginal;
copy->next = nextOriginal == nullptr
? nullptr
: nextOriginal->next;
original = nextOriginal;
}
return copyHead;
}
public:
Node* copyRandomList(Node* head) {
return copyByInterleaving(head);
}
};
题解¶
为什么沿 next 复制还不够¶
仅沿 next 创建一条值相同的新链表,只解决了节点顺序。若随后写 copy->random = original->random,
副本仍指向原节点,结果不是深拷贝;若按照 random 指向的值去找副本,重复值又会让目标身份不确定。
因此核心问题是把任意原节点引用翻译成它的唯一副本引用。random 可能向前、向后、自指或为空,赋值时
不能假定目标已经沿扫描方向处理完成。
方案一:显式保存地址映射¶
copyWithAddressMap 第一遍只创建节点,得到完整的 original -> copy 哈希映射;第二遍才翻译
next 与 random。先完成全部创建很重要:当 A.random 指向链尾 C 时,即使当前还没扫描到
C 的引用,映射中已经有 copy(C)。
映射键必须是原节点地址,而不是 val。它同时保证:每个原节点只创建一份副本、不同原节点即使同值也
不会合并、两条引用指向同一原节点时会落到同一个副本。
该方案时间 O(n)、逻辑直接,但映射额外保存 O(n) 对地址。链表 next 的固定顺序还提供了更强
结构,可以把这张映射临时编码在指针位置中。
方案二:让副本紧跟自己的原节点¶
第一遍在每个原节点后插入其副本:
原结构:A -> B -> C
穿插后:A -> a -> B -> b -> C -> c
此时任意原节点 X 的副本都能用 X->next 在常数时间取得,原地址到副本地址的映射不再需要哈希表。
创建 a 时先保存 B 为 nextOriginal,再改写 A.next,保证扫描仍能跳到下一个原节点。
第二遍为何能复制任意 random¶
穿插完成后,所有原节点的副本都已存在。若 A.random = C,那么 C.next 正是 c,所以:
a.random = A.random == null ? null : A.random.next
自指同样成立:C.random = C 会得到 c.random = C.next = c。空指针必须单独保留为空,不能解引用。
第二遍每次从原节点取得紧邻副本,处理后通过 copy->next 跳到下一原节点;此时 copy->next 仍保持
第一遍保存的原后继。
第三遍必须同时恢复两条链¶
穿插结构不是最终输出,也不能永久破坏调用者的原链。处理一组 original -> copy -> nextOriginal 时:
original->next = nextOriginal,恢复原链的一条边;若下一原节点存在,
copy->next = nextOriginal->next,连接到它的副本;否则副本链结束;移动到
nextOriginal,继续处理尚未拆分的交织后缀。
顺序依赖尚未删除的邻接编码。取得 nextOriginal 后再改两个 next,既不会丢失下一原节点,也能在它
仍与副本相邻时找到下一副本。
具体状态走读¶
阶段 |
|
已确定的 |
|---|---|---|
初始 |
|
只存在原节点引用 |
穿插 |
|
副本尚未连接 |
随机指针复制 |
交织结构保持 |
|
拆分 |
原链 |
全部只指向各自链内节点 |
主解选择、正确性与复杂度¶
三遍扫描后,每个副本由 new Node 独立创建;其 next 指向下一原节点的紧邻副本,random 指向
原随机目标的紧邻副本,因此两类边都与原结构一一对应且不含原引用。拆分还原了每条原 next 边,原链
保持不变。
公开入口采用穿插法:三次线性扫描,时间 O(n);除返回的新节点外只维护常数个指针,工作空间 O(1)。
显式映射法同为 O(n) 时间、额外 O(n) 空间,代码更直接,也适合不能临时修改原结构的场景。穿插法
的代价正是复制期间会短暂改写原链,因此并非在所有并发或只读环境中都更合适。