随机链表的复制
Copy List with Random Pointer
复制一条带 random 指针的链表，新链表的 next 和 random 都要指向新节点，不能指向原节点。
在力扣中练习题目描述
给你一个长度为 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或指向链表中的节点。
解题思路
哈希表 · 两遍复制
第一遍只建节点，第二遍用映射接两种边
复制值很容易，难的是 random：它可能指向还没创建的节点，也可能指回前面。直接边遍历边复制，很容易拿到原链表的指针。
把工作拆成两遍。第一遍只创建新节点，并建立 原节点 → 新节点 的映射；此时新节点之间还没有边。
第二遍再遍历原链表，用映射接边：next 和 random 都先查表，目标为空时显式写 null。这样无论 random 指向前面、后面还是 null，拿到的都是新节点。
再补 random：C0.random = C2；不能直接复用旧指针。
- cur
- O0
自拟主例的 random 同时包含前向（7 → 11）、后向（13 → 7）、相邻（11 → 10）和 null 四种情况；如果漏掉空值判断，map[nullptr] 会插入一个多余条目，甚至解引用空指针。
时间 O(n)，空间 O(n) 用于映射。
易错点
- 边遍历边复制 random：目标节点可能尚未创建，拿到的是旧指针。
- 不判断 cur->next / cur->random 是否为空，直接 map[...] 会插入空键。
- 复制后仍返回原 head：新链表没被返回，等于没复制。
代码与演示
head = [7,13,11,10]；random 分别指向 11、7、10、null原链表 4 个节点，next 依次连接；random 可能向前、向后或指向 null。
查看 C++ 代码
延伸阅读
- “先建节点、再连边”是复制图结构的通用套路，图和随机链表都适用。
- 如果要求 O(1) 额外空间，可以把新节点插到原节点后面，利用旧链的 next 当映射，最后再拆开；代价是代码更绕，而且会临时修改原链表。
- 判断复制是否成功，不能只看值：必须确认 next/random 指向的是新节点地址。