题目重点：复制next和random指针，使用原节点相邻的副本作为映射，完成后还原输入。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- next链无环，random只指本链节点或None；节点value可以重复，身份不能用value替代。O(1)指辅助空间不含新链输出。
- 允许临时改原next，但返回时恢复；不保证内存分配失败回滚，也不适合并发读原链或只读输入。
解题路线
- 第一轮把副本插在原节点之后，A→A′→B→B′。这样不建map也能从任意原节点x以x.next找到副本，保存原后继用于下一步。
- 第二轮遍历原节点，A′.random=A.random.next；random为None则None。此时所有副本已创建，所以随机前指/后指/self都可映射，不能在第一轮一边创建一边假设目标副本已存在。
- 第三轮拆分：原A.next恢复原B，副本A′.next设为B′。每步先保存clone，再恢复原指针，再建立副本next，避免丢掉中间节点。
- 空链返回None；最后节点要把copy.next设None。验证应核对副本没有任一原对象、邻接对应一致，以及原next/random保持不变，而不是只比较value序列。
- 若不能修改输入，hashmap两轮方案O(n)额外空间更合适。强异常安全可预先创建并记录节点再修改，但会失去当前O(1)辅助限制，需要讨论真正要求。
手动走一遍
A(value7)→B(value7)，A.random=B、B.random=B。副本值相同仍是两个不同对象，A′.random与B′.random都指B′。如果按value建立映射，两节点会被错误合并。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class Node:
def __init__(self,value,next=None,random=None):
self.value=value;self.next=next;self.random=random
def copy_random_list(head):
"""Acyclic next-chain; each random is None or a node in this chain.
O(1) auxiliary space excluding output. Temporarily mutates source, then restores.
Does not claim rollback safety for allocation failures or concurrent readers.
"""
current=head
while current:
current.next=Node(current.value,current.next);current=current.next.next
current=head
while current:
current.next.random=current.random.next if current.random else None
current=current.next.next
copied=head.next if head else None;current=head
while current:
clone=current.next;current.next=clone.next
clone.next=current.next.next if current.next else None
current=current.next
return copied
复杂度
三次线性遍历O(n)时间，辅助O(1)，输出n新节点O(n)。原链无环是终止前提；random不在链内时目标.next不代表已创建副本，需要改合同或用图拷贝。
易错点与追问
容易失分的边界
- 只拷贝next却让random仍指原链，不是深拷贝。
- 拆分中先覆盖当前next再取clone会丢失副本。
继续深挖
- next也可能成环时，为什么交织链表方案不再直接适用？
- 如果函数抛异常，调用方是否要求原链立即恢复？需要如何调整设计？
