0138. Copy List with Random Pointer
===================================
题目信息
--------
:题号: 0138. 复制带随机指针的链表
:难度: Medium
:主题: 链表、深拷贝、节点映射、原地穿插
:原题: `LeetCode 0138 `_
:重点: 先保证每个原节点有唯一副本,再复制两类引用;用相邻位置编码映射并在拆分时恢复原链
题目重述
--------
链表节点包含 ``val``、``next`` 和 ``random``。``next`` 指向下一个节点,``random`` 可以指向链表内任意
节点或为空。返回整条结构的深拷贝:每个原节点都对应一个全新副本,副本间的 ``next``、``random`` 关系
与原结构相同,返回结构中不能留下任何原节点引用。空链表返回 ``nullptr``。
自建示例
--------
.. code-block:: text
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++ 实现
--------
.. code-block:: cpp
#include
class Solution {
private:
Node* copyWithAddressMap(Node* head) {
if (head == nullptr) {
return nullptr;
}
std::unordered_map 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`` 的固定顺序还提供了更强
结构,可以把这张映射临时编码在指针位置中。
方案二:让副本紧跟自己的原节点
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
第一遍在每个原节点后插入其副本:
.. code-block:: text
原结构:A -> B -> C
穿插后:A -> a -> B -> b -> C -> c
此时任意原节点 ``X`` 的副本都能用 ``X->next`` 在常数时间取得,原地址到副本地址的映射不再需要哈希表。
创建 ``a`` 时先保存 ``B`` 为 ``nextOriginal``,再改写 ``A.next``,保证扫描仍能跳到下一个原节点。
第二遍为何能复制任意 ``random``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
穿插完成后,所有原节点的副本都已存在。若 ``A.random = C``,那么 ``C.next`` 正是 ``c``,所以:
.. code-block:: text
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``,既不会丢失下一原节点,也能在它
仍与副本相邻时找到下一副本。
具体状态走读
~~~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 阶段
- ``next`` 结构
- 已确定的 ``random``
* - 初始
- ``A -> B -> C``
- 只存在原节点引用
* - 穿插
- ``A -> a -> B -> b -> C -> c``
- 副本尚未连接
* - 随机指针复制
- 交织结构保持
- ``a -> c``、``b -> a``、``c -> c``
* - 拆分
- 原链 ``A -> B -> C``;副本链 ``a -> b -> c``
- 全部只指向各自链内节点
主解选择、正确性与复杂度
~~~~~~~~~~~~~~~~~~~~~~~~
三遍扫描后,每个副本由 ``new Node`` 独立创建;其 ``next`` 指向下一原节点的紧邻副本,``random`` 指向
原随机目标的紧邻副本,因此两类边都与原结构一一对应且不含原引用。拆分还原了每条原 ``next`` 边,原链
保持不变。
公开入口采用穿插法:三次线性扫描,时间 ``O(n)``;除返回的新节点外只维护常数个指针,工作空间 ``O(1)``。
显式映射法同为 ``O(n)`` 时间、额外 ``O(n)`` 空间,代码更直接,也适合不能临时修改原结构的场景。穿插法
的代价正是复制期间会短暂改写原链,因此并非在所有并发或只读环境中都更合适。