题干与适用场景
给定一条无环单链表的头节点。每个节点包含 val、next 和 random；random 可以为 null，也可以指向通过 next 可达的任意节点，包括当前节点本身。请返回一份深拷贝：每个原节点恰好对应一个新节点。如果原节点 x 的某个指针指向原节点 y，那么 x 的副本也必须通过同一字段指向 y 的副本。
节点值可以重复，因此值不能代表节点身份。next 链有限且无环，但 random 可以向前、向后指，也可以形成环。返回结果不能与输入共享节点；函数返回时，输入链表还必须保持原有结构。
这道题考数据结构与对象身份。基础解法用映射表记录“原节点到副本节点”；若追问要求常数辅助空间，可以暂时把副本插到原节点后面，完成指针赋值后再恢复输入。必需的输出节点不算辅助空间，但总内存仍然包含 O(n) 个新节点。
面试官考察点
第一个信号是能否从结构上定义深拷贝。值相等不够，必须存在从原节点到新节点的一一映射 f，并同时保持两类关系：x.next 的副本是 f(x).next，x.random 的副本是 f(x).random。
第二个信号是如何处理“引用目标还没被复制”的情况。只顺着链表走一遍并复制值，无法安全连接向前的 random。稳妥方案把分配和连线拆开：先创建所有目标节点，再通过身份映射连接指针。
第三个信号是能否推导空间优化。把每个副本紧跟在原节点之后，就建立了局部不变量：任一原节点 r 的副本恰好是 r.next。设置随机指针时，这个拓扑关系可以代替映射表。
最后要看输入恢复是否完整。交织法只有在恢复每个原节点的 next、抽出正确的副本链，并说明何时不能临时修改输入之后，才算完整答案。
回答前需要澄清的问题
random能否指向链表外？ 本题不能。如果外部节点也要复制，范围就变成一般的可达图；如果不复制，题目必须说明保留、清空还是拒绝外部引用。next能否成环？ 本题不能。若可以，仅沿next遍历且不记录已访问节点会永不结束，应改成图复制。- 能否临时修改输入？ 映射法完全不修改。交织法会临时修改，只适用于整个调用期间独占可变访问、且返回前能恢复原链表的情况。
- 额外空间如何计算？ 新节点是必需输出。映射表使用
O(n)辅助空间；交织法除输出外只使用O(1)个工作指针。 - 节点值唯一吗？ 不唯一。按值建映射会合并不同节点，必须按对象身份建映射。
- 空输入返回什么？ 返回
null。
30 秒回答框架
“我会先用原节点到副本节点的身份映射。第一遍创建全部副本，第二遍查表设置副本的 next 和 random，时间 O(n)、辅助空间 O(n)。如果要求常数辅助空间且允许临时修改输入，我会把每个副本插在原节点后面。这样任一随机目标的副本就是目标节点的下一个节点。第三遍拆开两条链并恢复输入。两种方案都是线性时间；交织法排除必需输出后只用 O(1) 辅助空间。”
分步骤深入解答
浅拷贝会直接复用原节点引用，因此不合格。只复制值同样不够：两个节点可能值相同，random 还可能指向尚未遍历到的节点。递归追随 random 也不是捷径，因为随机边可能成环。
最稳妥的基础方案显式建立一一映射。第一遍为每个原节点创建新对象；第二遍把两条出边都翻译到副本节点。也可以预先记录 null 对应 null，但面试中显式判空通常更清楚。
class RandomListNode {
val: number
next: RandomListNode | null
random: RandomListNode | null
constructor(
val: number,
next: RandomListNode | null = null,
random: RandomListNode | null = null,
) {
this.val = val
this.next = next
this.random = random
}
}
function copyWithMap(head: RandomListNode | null): RandomListNode | null {
if (head === null) return null
const copies = new Map<RandomListNode, RandomListNode>()
let current: RandomListNode | null = head
while (current !== null) {
copies.set(current, new RandomListNode(current.val))
current = current.next
}
current = head
while (current !== null) {
const copy = copies.get(current)!
copy.next = current.next === null ? null : copies.get(current.next)!
copy.random = current.random === null ? null : copies.get(current.random)!
current = current.next
}
return copies.get(head)!
}第一遍结束后的不变量很直接：沿 next 访问到的每个原节点，在映射中都有且只有一个不同的新节点，后续连线不会遇到尚未创建的目标。第二遍把从 x 到 y 的边翻译为从 f(x) 到 f(y)，结构因此被保留。两次线性遍历的时间是 O(n)，辅助空间是 O(n)。
若要去掉映射表，可以把对应关系临时编码进链表拓扑。先把：
A -> B -> C -> null变成：
A -> A' -> B -> B' -> C -> C' -> null此时 A' 就是 A.next。若 A.random 指向 C，那么 A'.random 应指向 A.random.next，也就是 C'。该关系不依赖节点值，所以向前、向后、自指和多个节点指向同一目标都能处理。
function copyByInterleaving(head: RandomListNode | null): RandomListNode | null {
if (head === null) return null
let current: RandomListNode | null = head
while (current !== null) {
const copy: RandomListNode = new RandomListNode(current.val, current.next)
current.next = copy
current = copy.next
}
current = head
while (current !== null) {
const copy: RandomListNode = current.next!
copy.random = current.random === null ? null : current.random.next
current = copy.next
}
const copiedHead = head.next
current = head
while (current !== null) {
const copy: RandomListNode = current.next!
const nextOriginal: RandomListNode | null = copy.next
current.next = nextOriginal
copy.next = nextOriginal === null ? null : nextOriginal.next
current = nextOriginal
}
return copiedHead
}正确性可以由三轮不变量得到。第一轮后，每个原节点后面紧跟唯一副本；第二轮中，副本的每条随机边都指向原目标之后的副本；第三轮每次恢复一条原链边，同时连接一条副本链边。循环结束后，原链完全恢复，从副本头可达的所有指针都只指向副本节点。
交织法做三次线性遍历，时间仍为 O(n)；除固定数量的工作指针外不存额外结构，因此辅助空间为 O(1)，但必需的 n 个输出节点仍占 O(n)。生产环境中它未必更好：前两轮期间，其他读者会看到被插入副本的输入；如果分离前抛出异常，链表可能停留在交织状态。映射法更容易审计，也适用于不可变或共享输入。
测试要分别验证结构、身份和恢复。至少覆盖：空链表；单节点且 random = null；单节点自指；重复值；两节点随机指针交叉；向前和向后的随机边；多个节点指向同一目标。复制后修改副本的值，确认原链不变；再次遍历输入确认 next 已恢复；再断言副本的 next 和 random 都不属于原节点集合。
高质量示范回答
“这题的关键是保留节点身份，而不只是复制值。值可能重复，随机边可能向前或成环，所以不能按值建映射，也不能在没有访问记录时递归追随机指针。
我的基础方案是用身份映射做两遍。第一遍沿无环的 next 链，为每个原节点创建一个副本；第二遍把两类指针都通过映射翻译过去。这样一一对应关系非常明确，时间线性、辅助空间线性。如果输入不可变、会被共享读取，或者实现可审计性更重要，我会选这个方案。
如果辅助空间必须为常数且允许临时修改，我会把副本插在每个原节点后面。这样任一原目标的副本就是它的 next，设置随机指针不再需要映射。最后必须拆开交替链：一边逐个恢复原链，一边连接副本链，确保结果没有任何指针回到输入。
我会说明交织、设置随机边、分离三步各自的不变量，并测试自指、重复值、交叉随机边、空输入和复制后的独立修改。两种方案都是 O(n) 时间；后一种是 O(1) 辅助空间，但仍需 O(n) 输出，而且不适合并发读者。”
常见错误
- 按节点值建映射 → 重复值会合并不同身份 → 用原节点对象作为键。
- 把原
random直接赋给副本 → 输出仍指回输入 → 把每个非空目标翻译成对应副本。 - 在一次普通前向遍历中边创建边直接连线 → 向前的随机目标可能还没创建 → 先创建全部节点，或用完整身份映射按需创建目标。
- 不记录访问状态就递归追随
random→ 随机环会造成无限递归或重复节点 → 本题只沿有限的next链遍历；一般图则使用已访问映射。 - 直接称交织法空间为
O(1)→ 返回值本身仍有n个新节点 → 明确说“排除必需输出后的O(1)辅助空间”。 - 没有判空就计算
current.random.next→ 空随机指针会报错 → 显式保留null。 - 只抽出副本链 → 原节点之间仍夹着副本 → 在同一轮分离中恢复原链并连接副本链。
- 对共享输入使用交织法 → 并发读者会观察到插入的节点 → 没有独占修改保证时使用映射法。
- 只比较节点值 → 浅拷贝也可能通过 → 验证对象身份、边的翻译、原链恢复和修改隔离。
追问及应对
追问一：如果输入从始至终都不允许修改呢？
使用身份映射方案。它的时间是 O(n)、辅助空间是 O(n)，整个执行过程都不触碰原链。按遍历下标复制到数组同样要 O(n) 空间；若输入没有稳定下标，还得建立身份到下标的映射。即使交织法最终会恢复，也违反“过程中不可修改”的更强约束。
追问二：如果 random 可以指向 next 链之外的节点呢？
先定义复制所有权。如果外部节点也要复制，输入就是一张有 next 与 random 两类出边的图，应使用 DFS 或 BFS 配合身份映射，让每个可达节点只创建一次。若外部节点应被共享，契约必须允许保留外部引用。交织法无法为任意外部目标发现或定位副本。
追问三：如果 next 也可以成环呢？
普通的判空循环不会结束。把两个字段都看成图的边，并维护已访问身份映射。首次发现节点时创建副本，再把未访问邻居加入队列。对可达图而言，时间与空间分别为 O(V + E) 和 O(V)；在本模型中每个节点最多有两条出边。
追问四：怎样证明它真的是深拷贝？
测试中同时遍历两条 next 链，建立仅用于断言的原节点到副本节点映射。检查长度和值相等、对象身份不同，并验证每条副本边都等于原目标映射后的节点。还要断言所有输出指针都不在原节点集合中。最后修改副本的值和指针，确认原链不变；对交织法，再逐一比较调用前后的原指针身份。
追问五：实际项目里会选择哪一种？
默认选择两遍映射法，因为对应关系显式，且不会暴露临时修改的输入。只有辅助内存确实构成约束、整个调用期间独占链表、失败处理还能保证恢复时，才选交织法。渐进空间更低，并不能消除并发安全、异常安全和维护成本。