138. 复制带随机指针的链表#
现实中的复制难题#
想象你在一个派对上负责给每位宾客发派对礼物。每位宾客除了认识自己前后的人（就像链表的next指针），还认识派对上的某个”神秘朋友”（就像random指针）。现在你需要在隔壁房间布置一个一模一样的派对，让每个人都有一个”分身”，并确保这些分身之间的所有社交关系都和原派对一样。这就是我们今天要解决的随机链表复制问题的真实写照。
问题描述#
题目目标#
给你一个长度为 n 的链表，每个节点包含一个额外的随机指针 random ，该指针可以指向链表中的任意节点或空节点。请构造这个链表的深拷贝，并返回拷贝链表的头节点。
示例 1#
输入： head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出： [[7,null],[13,0],[11,4],[10,2],[1,0]]
链表示意：
next: 7 -> 13 -> 11 -> 10 -> 1 -> null
random: node[0]=7 -> null
node[1]=13 -> index 0 (value 7)
node[2]=11 -> index 4 (value 1)
node[3]=10 -> index 2 (value 11)
node[4]=1 -> index 0 (value 7)说明： 返回深拷贝链表（next/random 关系与输入一致）
补充说明#
- 链表题的输入本质上是节点之间的连接关系，重点通常是返回处理后的头节点或目标节点。
问题定义与难点分析#
LeetCode 第138题”复制带随机指针的链表”要求我们对一个特殊的链表进行深拷贝。这个链表的每个节点除了包含指向下一个节点的next指针，还包含一个random指针，可以指向链表中的任意节点或null。
// 节点定义
class Node {
int val;
Node next;
Node random;
}为什么这题不简单？#
让我们先深入理解问题的难点：
-
循环依赖问题：就像派对上的人际关系一样，如果A的神秘朋友是B，B的神秘朋友是C，C的神秘朋友是A，这种循环依赖关系让我们无法简单地”一次性”完成复制。
-
节点映射难题：当我们复制节点A’时，如果它的random指针指向节点B，而B还没有被复制，我们就陷入了”先有鸡还是先有蛋”的困境。
-
空间效率考虑：如何在不使用额外空间的情况下，记住原节点和复制节点之间的对应关系？
解决思路的演进#
让我们像解开一团缠绕的毛线一样，一步步理清解决方案：
方案一：哈希表映射法#
就像在派对上给每个人发一个编号，然后在隔壁房间按编号复制人际关系。
具体步骤：
- 第一遍遍历：创建所有节点的复制，并用哈希表记录原节点到新节点的映射关系
- 第二遍遍历：根据哈希表中的映射关系，设置所有新节点的next和random指针
这种方法简单直观，但需要额外的存储空间。
方案二：节点交织法#
这是一个巧妙的思路，就像让每个人的分身直接站在他们身后，这样就能轻松找到对应关系。
具体步骤：
- 第一遍遍历：在每个原节点后面创建它的复制节点
- 第二遍遍历：设置所有复制节点的random指针
- 第三遍遍历：分离原始链表和复制链表
这种方法不需要额外空间，但需要三次遍历。
方案三：优化的节点标记法（一种特殊情况下的思路）#
如果节点值的范围允许，我们可以用一些特殊的标记方式来记录节点间的对应关系。 但这种方法依赖于具体的数值范围限制，不是通用解法。
详细代码实现#
让我们先来看哈希表映射法的实现，它最容易理解：
public Node copyRandomList(Node head) {
// 边界处理：空链表直接返回 null
if (head == null) {
return null;
}
// nodeMap：记录“原节点 -> 复制节点”的映射，解决 random 指向难题
Map<Node, Node> nodeMap = new HashMap<>();
// 第一遍：只复制节点本体（值），先不连 next/random
Node curr = head;
while (curr != null) {
// 为当前原节点创建对应副本并存入映射
nodeMap.put(curr, new Node(curr.val));
// 继续遍历原链表
curr = curr.next;
}
// 第二遍：根据映射关系补齐副本节点的 next 和 random
curr = head;
while (curr != null) {
// 取出当前原节点对应的副本节点
Node newNode = nodeMap.get(curr);
// 建立 next 映射；若 curr.next 为 null，map.get(null) 结果也是 null
newNode.next = nodeMap.get(curr.next);
// 建立 random 映射；random 可能为 null，同理安全
newNode.random = nodeMap.get(curr.random);
// 继续处理下一个原节点
curr = curr.next;
}
// 返回原头节点对应的副本头节点
return nodeMap.get(head);
}再来看空间优化的节点交织法：
public Node copyRandomList(Node head) {
// 边界处理：空链表直接返回 null
if (head == null) {
return null;
}
// 第一步：把复制节点插入到每个原节点后面（原1->原2 变为 原1->拷1->原2->拷2）
Node curr = head;
while (curr != null) {
// 创建当前原节点的副本
Node copy = new Node(curr.val);
// 副本先接上原来的后继
copy.next = curr.next;
// 原节点再指向副本，完成“交织”
curr.next = copy;
// 跳到下一个原节点（即 copy.next）
curr = copy.next;
}
// 第二步：设置每个副本节点的 random
// 若原节点 random 指向 R，则副本 random 应指向 R 的副本（即 R.next）
curr = head;
while (curr != null) {
if (curr.random != null) {
curr.next.random = curr.random.next;
}
// 每次跨过“原+拷”两个节点，进入下一个原节点
curr = curr.next.next;
}
// 第三步：拆分交织链表，恢复原链表并提取复制链表
curr = head;
// copyHead：复制链表头（就是原 head 后面的第一个副本）
Node copyHead = head.next;
// currCopy：遍历复制链表用的指针
Node currCopy = copyHead;
while (curr != null) {
// 恢复原链表：原节点 next 指回下一个原节点
curr.next = curr.next.next;
// 连接复制链表：副本节点 next 指向下一个副本节点
if (currCopy.next != null) {
currCopy.next = currCopy.next.next;
}
// 两条链表各自前进
curr = curr.next;
currCopy = currCopy.next;
}
// 返回复制链表头
return copyHead;
}复杂度分析与比较#
哈希表映射法：
- 时间复杂度：O(n)，需要两次遍历
- 空间复杂度：O(n)，需要哈希表存储映射关系
- 优点：实现简单，思路清晰
- 缺点：需要额外空间
节点交织法：
- 时间复杂度：O(n)，需要三次遍历
- 空间复杂度：O(1)，不需要额外空间
- 优点：空间效率高
- 缺点：需要修改原链表结构（虽然最后会恢复）
实际应用思考#
这种深拷贝问题在实际开发中非常常见：
- 对象的深拷贝
- 图结构的复制
- 系统快照的创建
- 游戏存档的复制
核心技巧总结#
- 复杂问题分解：将问题分成创建节点和建立关联两个子问题
- 空间换时间：用哈希表简化实现
- 就地修改：通过调整链表结构省略额外空间
- 分步骤处理：避免处理循环依赖导致的复杂性
小结#
随机链表的复制问题教会我们：
- 如何处理带有复杂引用关系的数据结构
- 空间和时间效率的权衡思想
- 通过临时修改数据结构解决复杂问题
- 如何优雅地处理循环依赖问题
这道题是链表、哈希表和深拷贝概念的完美结合，它启发我们：
- 在处理复杂数据结构时，可以考虑分步骤进行
- 临时的数据结构修改有时能带来意想不到的便利
- 空间与时间的权衡是算法设计中永恒的主题
记住：解决复杂问题如同复制一场精心安排的派对，关键在于理清依赖关系，合理安排执行顺序！