138. 随机链表的复制 (Medium)
专题归类： 04-链表 LeetCode 链接： https://leetcode.cn/problems/copy-list-with-random-pointer/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个长度为 n 的链表，每个节点包含一个额外的随机指针 random，该指针可以指向链表中的任意节点或 null。
构造这个链表的深拷贝。深拷贝应该由 n 个全新节点组成，每个新节点的值都设为其对应的原节点的值，新节点的 next 和 random 指针都应指向对应新节点。
示例：
- 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
- 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
题目详细分析
- 数据范围： 链表长度 [0, 1000]，节点值 [-10^4, 10
- 输入特征： 每个节点有两个指针：next（指向后继）和 random（指向任意节点或 null）
- 核心约束： 必须深拷贝——新链表的所有节点都必须是全新创建的，不能与原节点共用
- 隐藏条件： random 指向的是原链表的节点，而我们需要在新链表中建立对应的引用关系——关键在于建立「原节点 → 克隆节点」的映射
- 边界条件： 空链表、random 指向 null、random 指向自身、random 形成交叉引用
小白版直白理解
就像你要复印一份文件，但这份文件里有些注释（random 指针）指向文件的其他部分。普通复印只能复制文字（val）和页码顺序（next），但那些「指向其他部分」的注释在新文件里也需要正确指向对应的新位置。
所以我们需要先复制所有页（克隆节点），然后记下每个原页面和它对应的复印页面之间的对应关系，这样才能把注释中的「指向原第 X 页」变成「指向复印版第 X 页」。
解题思路
思路一：三步法（插入克隆 → 设置 random → 拆分，O(1) 空间，推荐）
为什么这样想： 不用哈希表，而是利用原链表的 next 指针来建立映射关系。在每一个原节点后面插入其克隆节点，这样原节点到克隆节点的映射关系天然地通过 next 指针建立起来：原节点.next = 克隆节点。那么原节点.random.next 就是克隆节点的 random 指向。
关键洞察： 克隆节点.random = 原节点.random.next。因为原节点.random 指向原链表的某个节点，该节点的 next 就是对应的克隆节点。这样不需要额外空间就完成了 random 指针的设置。
def copyRandomList(head):
"""三步法：插入克隆 → 设置 random → 拆分"""
if not head:
return None
# 第一步：在每个原节点后插入克隆节点
cur = head
while cur:
clone = Node(cur.val)
clone.next = cur.next
cur.next = clone
cur = clone.next # 跳到原链表的下一个节点
# 第二步：设置克隆节点的 random 指针
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next # 关键！原节点.random 的 next 就是对应的克隆节点
cur = cur.next.next # 一次跳两步，跳过克隆节点
# 第三步：拆分链表
cur = head
new_head = head.next # 保存克隆链表的头
while cur:
clone = cur.next
cur.next = clone.next # 恢复原链表的 next
if clone.next:
clone.next = clone.next.next # 连接克隆链表的 next
cur = cur.next # cur 已经是原链表的下一个节点
return new_head思路二：哈希表法（更直观）
思路讲解： 用字典建立「原节点 → 克隆节点」的映射。第一遍遍历创建所有克隆节点并建立映射；第二遍遍历根据映射设置克隆节点的 next 和 random 指针。思路直观，但需要 O(n) 空间。
def copyRandomList(head):
"""哈希表法"""
if not head:
return None
mapping = {} # 原节点 → 克隆节点
# 第一遍：创建所有克隆节点
cur = head
while cur:
mapping[cur] = Node(cur.val)
cur = cur.next
# 第二遍：设置 next 和 random
cur = head
while cur:
mapping[cur].next = mapping.get(cur.next)
mapping[cur].random = mapping.get(cur.random)
cur = cur.next
return mapping[head]思路三：回溯 + 哈希表（递归法）
思路讲解： 用递归的方式处理每个节点。如果节点已被克隆则直接从哈希表返回；否则创建克隆节点，递归处理 next 和 random。这种方法天然地处理了可能存在的环（random 指向已访问节点）。
def copyRandomList(head):
"""递归 + 哈希表"""
mapping = {}
def dfs(node):
if not node:
return None
if node in mapping:
return mapping[node]
# 创建克隆节点
clone = Node(node.val)
mapping[node] = clone
# 递归处理 next 和 random
clone.next = dfs(node.next)
clone.random = dfs(node.random)
return clone
return dfs(head)易错点
- 三步法的拆分步骤： 拆分时不仅要恢复原链表的 next，还要正确设置克隆链表的 next，两个链表要同时恢复
- random 为 null 的情况：
cur.random.next会崩溃，必须先判断if cur.random。哈希表法中用mapping.get(cur.random)返回 None 处理 - 三步法第二步的遍历： 用
cur.next.next跳过一个偶数步（原→克隆→原→克隆），不是cur = cur.next - 拆分时 clone.next 的判断： 当 clone.next 不存在时，说明到了链表末尾，不能访问 clone.next.next
- 深拷贝的含义： 新链表的每个节点都是新创建的对象，原链表的修改不应影响新链表
框架提炼
三步法模板： 适用于需要建立原节点和克隆节点一一对应关系的场景。
def copy_list(head):
if not head:
return None
# 1. 插入克隆节点
cur = head
while cur:
clone = Node(cur.val)
clone.next = cur.next
cur.next = clone
cur = clone.next
# 2. 设置特殊指针
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
# 3. 拆分
cur = head
new_head = head.next
while cur:
clone = cur.next
cur.next = clone.next
if clone.next:
clone.next = clone.next.next
cur = cur.next
return new_head三步法的核心思想是「借用原链表结构存储映射关系」，避免了额外的哈希表空间。这个思路也可以用于其他需要「复制结构」的问题。