Leecode热题100：随机链表的复制（链表）
目录
方案二：利用“空间拓扑”消除映射 (Interweaving)
题目描述：
给你一个长度为 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]]
（来源：leecode）
要解决“带有随机指针的链表深拷贝”问题，我们不仅是在写代码，而是在处理信息映射和内存拓扑的问题。
拆解本质：什么是“深拷贝”？
从物理层面看，链表是一组分散在内存中的节点。深拷贝意味着：
- 数量对等：原链表有 n 个节点，新链表也必须有 n 个。
- 数值一致：对应的节点
val必须相同。 - 拓扑一致：最关键的一点，新节点的
next和random必须指向新链表中的对应节点，而不是原链表。
核心矛盾点
当我们遍历原链表到达节点 A 时，我们需要设置 A'.random。
如果 A.random 指向节点 B，而 B 在链表的末尾，此时我们还没创建 B'。
矛盾点在于： 在单次线性遍历中，我们无法引用一个“尚未存在”的对象。
方案一：利用“映射”打破时空限制 (Hash Map)
如果我们想在一次或两次遍历中解决问题，我们需要一个“记忆体”来存储原节点与新节点之间的对应关系。
- 原子逻辑：给定原地址 Pold，我必须能立刻找到对应的新地址 Pnew。
- 工具选择：
std::unordered_map<Node*, Node*>。
思路过程：
- 第一遍遍历：把所有新节点创建出来，并把
(原节点地址, 新节点地址)存入哈希表。 - 第二遍遍历：根据哈希表，把新节点的
next和random指针连接起来。
评价：这是最直观的逻辑，时间复杂度 O(n)，空间复杂度 O(n)。
方案二：利用“空间拓扑”消除映射 (Interweaving)
如果我们追求极致，不使用额外的哈希表（即 O(1) 空间复杂度），该怎么办？
回到第一性原理：映射的本质是建立关联。 除了哈希表，还有什么方式能让原节点和新节点产生物理关联？
天才的想法：把新节点直接“嫁接”在原节点后面。
思路过程：
第一步：复制并嵌入 (Copy & Insert)
将每个新节点 A' 插入到原节点 A 和 A.next 之间。
- 原结构：A -> B -> C
- 新结构：A -> A' -> B -> B' -> C -> C'本质：现在 A' 的位置就在 A 的旁边。这意味着 A.next 就是 A'。
第二步：复制随机指针 (Copy Random)
因为 A' 紧跟在 A 后面，那么 A.random 的拷贝（即 A'.random）一定就在 A.random.next 的位置。
- 逻辑：
A->next->random = A->random->next(需注意判空)。
第三步：拆解链表 (Split)
将这个长链表拆分为原链表和新链表，恢复原貌并提取拷贝。
C++ 代码实现 (基于方案二)
这是最体现算法功底的解法。我们一步步用代码实现上述思维：
/* // 节点定义 class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { if (!head) return nullptr; // --- 第一阶段：在每个原节点后面创建一个新节点 --- // 原：A -> B -> C // 现：A -> A' -> B -> B' -> C -> C' Node* curr = head; while (curr) { Node* newNode = new Node(curr->val); newNode->next = curr->next; curr->next = newNode; curr = newNode->next; } // --- 第二阶段：设置新节点的 random 指针 --- // 核心逻辑：A'.random = A.random->next curr = head; while (curr) { if (curr->random) { curr->next->random = curr->random->next; } curr = curr->next->next; // 移动到下一个原节点 } // --- 第三阶段：将交错的链表拆开 --- // 恢复原链表，提取新链表 Node* newHead = head->next; curr = head; Node* copyCurr = newHead; while (curr) { curr->next = curr->next->next; // 恢复原链表连接 if (copyCurr->next) { copyCurr->next = copyCurr->next->next; // 提取新链表连接 } curr = curr->next; copyCurr = copyCurr->next; } return newHead; } };用第一性原理思考这道题的轨迹是：
- 明确原子目标：创建 n 个独立节点，并复制复杂的指向关系。
- 识别瓶颈：
random指针指向的对象在创建当前节点时可能尚未就绪，或无法通过当前指针直接定位。 - 寻找关联媒介：
- 方案一：使用外部内存（哈希表）作为媒介。
- 方案二：使用内部物理位置（交错排列）作为媒介。
如果理解了“如何建立 A 与 A' 的稳定关联”，你就真正掌握了这道题的精髓。
面试回答
第一步：明确本质
“首先，这道题的本质是处理带有复杂拓扑关系的内存拷贝。普通的单链表深拷贝只需要线性遍历，但这里的 random 指针打破了线性的顺序，它可能指向之后还没创建的节点，也可能指向之前的节点。”
第二步：提出矛盾
“这里的核心矛盾在于：
当我在克隆节点 A 时，我无法立刻确定它的 random 指针应该指向哪里，因为被指向的节点 B 可能还没被创建，或者我无法在 $O(1)$ 时间内找到 B 的克隆体。”第三步：从直觉出发
“为了打破这个瓶颈，我首先想到的是建立映射关系：
- 思路：使用一个哈希表（Hash Map），以原节点地址为 Key，新节点地址为 Value。
- 过程：第一遍遍历创建所有节点并存入 map，第二遍根据 map 连接
next和random。 - 评价：这个方案的时间复杂度是 O(n)，非常高效，但它需要 O(n) 的额外空间来存储哈希表。”
第四步：极致优化（空间换位置）
“如果面试官要求空间复杂度优化到 O(1)，我就需要利用原有的物理空间来存储映射关系，也就是所谓的‘原地交错法’：
- 节点嫁接：我遍历原链表，把每个克隆节点 A' 直接插入到原节点 A 的后面。这样，原节点和新节点就成对出现了。
- 关系同步：此时，映射关系隐含在位置中。如果 A.random 指向 B，那么 A' 的 random 就应该指向 B 的后继节点（即 B'）。这一步我们只需要一次遍历就能完成。
- 链表拆分：最后，通过‘跳跃式’重新连接指针，将交错的链表还原为原链表和拷贝链表。
第五步：总结复杂度
“这种方案的精妙之处在于，它通过改变链表的物理结构，用 O(1) 的辅助空间巧妙地替代了哈希表的映射功能，同时时间复杂度依然保持在 O(n)。”
面试官可能会追问的细节：
- Q: 拆分链表（第三步）时需要注意什么？
- A: 需要注意空指针（
nullptr）的处理，尤其是当curr->next是最后一个节点时，要确保不要访问nullptr->next。
- A: 需要注意空指针（
- Q: 哈希表法和交错法哪个更好？
- A: 在工程实践中，哈希表法代码更简洁、易维护，不容易出错；在对内存极其敏感的嵌入式或底层开发中，交错法（O(1) 空间）更有优势。
