随机链表的复制

怎样从“复制带 random 指针的链表 [[7,null],[13,0],[11,4],[10,2],[1,0]]。”推导出 链表 · 哈希克隆，并证明每次状态变化都不会漏掉答案？

中心结论：第一遍 old→new 入 map;第二遍按 map 连接 next 与 random。

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的 深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

在本站主例中，复制带 random 指针的链表 [[7,null],[13,0],[11,4],[10,2],[1,0]]。

算法最终需要得到或观察：新链结构与原链同构,结点为新对象。

只用一种结构往往让某个操作退化为线性；组合结构让查找、更新和顺序维护共享同一份状态。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“数据结构控制台”，明确答案需要观察什么。
2. 2状态只维护 原链扫描指针、克隆 map、新链尾指针。
3. 3转移每一步按照 第一遍 old→new 入 map;第二遍按 map 连接 next 与 random。
4. 4收尾读取 新链结构与原链同构,结点为新对象。，并复核边界与复杂度。

为每个操作写出复杂度目标，再反推需要组合哪些数据结构。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：原链扫描指针、克隆 map、新链尾指针。

这道题严格意义上是数据结构题，根据给定的数据结构，对它进行深拷贝。 先将每个节点都复制一份，放在它的 next 节点中。如此穿插的复制一份链表。

再将穿插版的链表的 random 指针指向正确的位置。

再将穿插版的链表的 next 指针指向正确的位置。最后分开这交织在一起的两个链表的头节点，即可分开 2 个链表。

第一遍 old→new 入 map;第二遍按 map 连接 next 与 random。

执行过程中持续维护：原链扫描指针、克隆 map、新链尾指针。

正确性依赖以下不变量：map 保证每个旧结点恰有一个新副本。

面试时可以压缩为：哈希表两遍:第一遍克隆结点入 map,第二遍用 map 连 next/random;也可交错复制 O(1) 空间。

落到当前题，执行机制可以压缩为：第一遍 old→new 入 map;第二遍按 map 连接 next 与 random。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入复制带 random 指针的链表 [[7,null],[13,0],[11,4],[10,2],[1,0]]。 因为：第一遍 old→new 入 map;第二遍按 map 连接 next 与 random。
2. 2哈希映射 old → clone深拷贝带 random 指针链表。 因为：无 map 无法 O(1) 找 clone。
3. 3clone 结点 13 → 113第一遍创建 clone。 因为：第二遍设置 random。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5clone 结点 10 → 110第一遍创建 clone。 因为：第二遍设置 random。
6. 6clone 结点 1 → 101第一遍创建 clone。 因为：第二遍设置 random。
7. 7深拷贝链表完成返回 clone 头。 因为：LC138 标准解法。
8. 8收尾与复杂度新链结构与原链同构,结点为新对象。 因为：时间 O(n) · 空间 O(n)。第一遍 old→new 入 map;第二遍按 map 连接 next 与 random。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// Node define
type Node struct {
	Val    int
	Next   *Node
	Random *Node
}

func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}
	tempHead := copyNodeToLinkedList(head)
	return splitLinkedList(tempHead)
}

func splitLinkedList(head *Node) *Node {
	cur := head
	head = head.Next
	for cur != nil && cur.Next != nil {
		cur.Next, cur = cur.Next.Next, cur.Next
	}
	return head
}

func copyNodeToLinkedList(head *Node) *Node {
	cur := head
	for cur != nil {
		node := &Node{
			Val:  cur.Val,
			Next: cur.Next,
		}
		cur.Next, cur = node, cur.Next
	}
	cur = head
	for cur != nil {
		if cur.Random != nil {
			cur.Next.Random = cur.Random.Next
		}
		cur = cur.Next.Next
	}
	return head
}

func main() {
    // 1. 主例
    //    输入：mode="copy-random-list", values=[7,13,11,10,1]
    //    期望：新链结构与原链同构,结点为新对象。
    //
    // 2. 失败 / 未命中
    //    检查：第二遍才连 random,第一遍只创建结点。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC133 克隆图；LC146 LRU Cache
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意复制带 random 指针的链表 [[7,null],[13,0],[11,4],[10,2],[1,0]]。
2. 2重复只用一种结构往往让某个操作退化为线性；组合结构让查找、更新和顺序维护共享同一份状态。
3. 3优化第一遍 old→new 入 map;第二遍按 map 连接 next 与 random。
4. 4证明map 保证每个旧结点恰有一个新副本。
5. 5复杂度时间 O(n)，空间 O(n)