随机链表复制详解：深拷贝原理与哈希表、原地复制等解法

刷 LeetCode Hot 100 的朋友，几乎都会在“链表”这一块撞见 138 题《随机链表的复制》。这道题在面试里的出现频率相当高，字节、微软、腾讯、阿里都有考过它的原题或变体。题目本身不复杂，但对链表的理解、对深拷贝和浅拷贝的概念、以及对引用关系的处理能力，要求得很细。很多人是“看答案五分钟就懂了，自己写半小时卡住”，问题往往出在 random 指针的处理上。这篇文章我按自己刷题和复盘的实际思路来讲，把哈希表法、原地复制法、递归法三种写法全部拆开，附带复杂度分析和避坑经验，希望能帮你一次性吃透这道题。

1. 题目到底在考什么

1.1 先看原题长什么样

题目给的是一个特殊的链表节点，除了常规的 next 指针之外，还多了一个 random 指针，这个 random 可以指向链表中的任意一个节点，也可以指向 null。要求你返回一个全新的链表，这个新链表和原链表结构完全一样，每个节点的值和 random 指向关系都要一一对应，但所有节点都得是新建的，不能直接复用原链表的节点。

class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random

这里面的坑很隐蔽：只复制 next 的话，遍历一遍把值一个个填进去就行，但 random 指针不是像 next 那样沿着一个方向就能走完的，它可以乱序指向任意位置，甚至指向自己。

1.2 深拷贝和浅拷贝的本质区别

很多新手在拿到这道题时，第一反应是“我直接遍历原链表，然后 new 一个新节点不就行了”。但问题在于：如果你只是把node.random这个引用原封不动地赋值给新节点，那新链表里的 random 指向的仍然是原链表的节点，而不是新链表里对应的节点。这样拷贝出来的是一个“半成品”，跟原链表共享了部分节点，修改任何一边的 random 节点内容，另一边也会跟着变。这在面试里叫浅拷贝。

深拷贝的要求是：原链表里任意一个节点，都要在内存里单独复制一份；原链表里任意两个节点之间的引用关系，在新链表里也要原样重建。也就是说，原链表第 3 个节点的 random 指向原链表第 5 个节点，那么新链表第 3 个新节点的 random 就要指向新链表第 5 个新节点。

1.3 难点的根因：random 指针的“延迟绑定”

你动手写代码时会发现一个尴尬的问题：第一遍遍历链表时，你从头到尾创建新节点，但创建第 1 个新节点时，可能它的 random 指向的是第 5 个节点，而第 5 个新节点还没创建出来。这就是 random 指针的“延迟绑定”问题——它的目标位置在当时是不可知的。

所以这道题真正考察的是：你怎么建立一种映射关系，把原链表里的每一个节点“翻译”成新链表里对应的节点，然后再根据这个映射关系去连接 random。只要把这个核心想透了，后面各种解法都是围绕“映射”这两个字展开的。

提示：这道题还有一个容易踩的坑——题目里说的 random 指针可以指向 null。很多代码在处理 next 和 random 时只判断了非空情况，一旦遇到 null 就会报错，后面我会专门讲这个问题。

2. 解法一：哈希表映射法，最推荐也最好理解

2.1 核心思路：用字典把“翻译关系”记下来

哈希表法最直白，思路分三步：

1. 第一趟遍历：顺着 next 指针走一遍原链表，每遇到一个原节点，就创建一个与之对应的新节点，然后用一个字典把原节点 -> 新节点的映射关系存下来。这一步不管 random，只负责“造人”。
2. 第二趟遍历：再走一遍原链表，这次利用字典，把每个新节点的 next 和 random 都接上。node_map[cur].next = node_map[cur.next]，意思是“当前原节点的下一个原节点，对应到新链表里就是当前新节点的下一个新节点”。
3. 最后返回node_map[head]，也就是原链表头节点对应的新链表头节点。

这个思路像什么？像我们翻译外语文章：先把每个词对应的中文意思记在一个词表里，再把整个句子按词表重新组装。原链表节点的关系没有被破坏，字典就是中间那座桥。

2.2 Python 代码实现

class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': if not head: return None node_map = {} cur = head # 第一趟：创建新节点，建立原节点到新节点的映射 while cur: node_map[cur] = Node(cur.val) cur = cur.next # 第二趟：根据映射关系，设置新节点的 next 和 random cur = head while cur: if cur.next: node_map[cur].next = node_map[cur.next] if cur.random: node_map[cur].random = node_map[cur.random] cur = cur.next return node_map[head]

2.3 复杂度与优缺点

时间复杂度和空间复杂度都是 O(n)，n 是链表长度。

这个解法的优点非常突出：逻辑简单、代码量小、不容易写出 bug，面试时是最稳妥的选择。空间换时间，用 O(n) 的额外空间换来了 O(n) 的清晰实现。缺点只有一个——空间复杂度不是最优的，如果面试官要求原地完成或者说“你能不能用 O(1) 的额外空间”，那就需要下面的原地复制法。

2.4 关键细节：为什么两次遍历而不是一次

有人会问：我能不能第一遍创建新节点的时候，就顺手把 next 和 random 都接上？答案是不能。因为创建当前新节点的时候，它的 random 可能指向一个还没被创建出来的节点。你要么提前把所有节点都创建好，要么在字典里记录这个关系，等目标节点创建完再去补接。

这正是哈希表法的精髓：第一趟遍历解决“节点存在性”的问题，第二趟遍历解决“关系连接”的问题。两个问题分开处理，复杂度没有增加，但逻辑清晰很多。这也是为什么我在面试中优先推荐哈希表法——不容易在紧张的面试环境里翻车。

3. 解法二：原地复制法，O(1) 空间也能搞定

3.1 核心思路：把新节点插在原节点后面

哈希表法虽然好理解，但用了额外空间。如果面试官要求空间复杂度降到 O(1)，就得换思路了。原地复制法的经典技巧是“链表穿插”：

第一步：遍历原链表，在每个原节点后面插入一个它的复制节点。比如原链表是 A -> B -> C，插入后变成 A -> A' -> B -> B' -> C -> C'。这一步，A' 就是 A 的复制品，B' 就是 B 的复制品，以此类推。

第二步：再遍历一遍链表，给所有的复制节点设置 random 指针。因为 A' 紧紧跟在 A 后面，所以 A 的 random 指向谁，A' 的 random 就指向那个节点的后一个节点。具体操作是：如果 cur.random 不为空，那么cur.next.random = cur.random.next。

第三步：把链表拆成两个。奇数位是原链表，偶数位是新链表。遍历一遍，把连接关系恢复原状，返回新链表的头节点。

3.2 Python 代码实现

class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': if not head: return None # 第一趟：在每个原节点后面插入复制节点 cur = head while cur: new_node = Node(cur.val) new_node.next = cur.next cur.next = new_node cur = new_node.next # 第二趟：设置复制节点的 random 指针 cur = head while cur: if cur.random: cur.next.random = cur.random.next cur = cur.next.next # 第三趟：拆分链表，还原原链表并拿出新链表 cur = head new_head = head.next while cur: copy_node = cur.next cur.next = copy_node.next if copy_node.next: copy_node.next = copy_node.next.next cur = cur.next return new_head

3.3 为什么这个办法能正确设置 random

第二趟里那句cur.next.random = cur.random.next是原地法的灵魂。你想一下：在原链表里，任意一个原节点 N，它的复制节点 N' 就在 N 的 next 位置。如果原节点 N 的 random 指向节点 M，那么 M 的复制节点 M' 也在 M 的 next 位置。所以 N' 的 random 就应该指向 M'，也就是 M.next，在代码里就写成了cur.random.next。

用图来表示更直观：原链表中 N.random = M，那么在穿插后的链表中，N.next 是 N'，M.next 是 M'，我们想让 N'.random = M'。因为 M' 的位置就是 M 的 next，所以自然有cur.next.random = cur.random.next。这个关系在整个穿插后的链表中是恒成立的，只要原链表不是空链表，这个映射就一直有效。

3.4 易错点：拆链表时别把原链表弄断

第三趟拆分是整个解法里最容易写错的地方。有一个很典型的错误写法：把cur.next = copy_node.next和copy_node.next = copy_node.next.next写反了，或者少写一个判断，导致原链表被破坏或者新链表里出现循环引用。

我实际写的时候习惯这样处理：先保存copy_node = cur.next，然后把原链表的 next 还原为copy_node.next；接着判断copy_node.next是否为空，如果不为空，就把复制链表的 next 指向copy_node.next.next；最后cur = cur.next继续遍历原链表。这个过程本质上是在把一条“A A' B B' C C'”链重新拆成两条独立链，注意边界条件，特别是链表结尾处 copy_node.next 可能为 None。

注意：原地复制法虽然空间复杂度是 O(1)，代码也能写对，但面试时讲起来比哈希表法复杂，容易在第二趟、第三趟的逻辑上绕晕。我建议你平时两种方法都练熟，但面试时如果面试官没有特别要求，优先讲哈希表法。

4. 解法三：递归法，理解用，面试慎用

4.1 递归思路与代码

递归法本质上还是借助哈希表，只不过用递归函数代替了循环遍历。核心思想是：copyRandomList这个函数的返回值是“给定一个原节点，返回它的复制节点”。当递归处理一个节点时，先创建该节点的复制节点并记录到字典里，再递归处理它的 next 和 random。

class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': node_map = {} def dfs(node): if not node: return None if node in node_map: return node_map[node] new_node = Node(node.val) node_map[node] = new_node new_node.next = dfs(node.next) new_node.random = dfs(node.random) return new_node return dfs(head)

4.2 递归法的价值

递归法最巧妙的地方在于用了“记忆化搜索”：一个节点只创建一次，后续再遇到直接返回已创建的复制节点。这就天然解决了 random 指向已创建节点的情况。它避免了显式的两趟循环，代码更精简。

但这个解法有两个明显问题：

一是链表的深度如果很大，递归可能导致 Python 的递归深度超限，出现 RecursionError。虽然 LeetCode 的测试用例一般不会太深，但实际生产环境或者面试中手写递归，很容易触及这个问题。

二是在面试时递归的思维链路比循环更绕。面试官如果追问“递归的调用栈空间也算空间复杂度”，你很难说清楚。所以递归法适合用来加深理解，但在面试实战中，我一般不会主动把它作为首选答案。

5. 三种解法对比与刷题建议

5.1 复杂度与代码量对比

时间上三种方法没有本质差别，都是 O(n)，因为每个节点都只被处理常数次。但空间上差别明显：哈希表法和递归法需要 O(n) 的额外空间，原地复制法只需要几个临时指针。

5.2 面试时怎么选

我的习惯是分情况。

如果面试官没有做任何空间限制，我直接讲哈希表法。它最好理解、最不容易写错，面试官也最容易跟进你的思路。我会把两层循环的逻辑讲清楚：第一层“建映射”，第二层“接指针”。

如果面试官追问“能不能优化空间复杂度”，我再切换到原地复制法。切换的时候我会先说清楚核心技巧——“把复制节点插在原节点后面，这样 random 的映射就变成了相对位置映射”，然后再动手写代码。这样面试官会认为你对两种方案都有真正的理解，而不是只会背答案。

如果面试官进一步问“递归怎么写”，我才会提递归法，并且会主动说明它的递归栈空间限制。这样既展示了知识广度，又体现了工程思维。

5.3 从这道题迁移出去的知识点

这道题的核心套路是“构建新旧节点之间的映射关系”，这个思路可以迁移到很多场景：

• 图的深拷贝：给一个图，返回它的深拷贝，本质也是新旧节点的映射。
• 复杂对象的序列化与反序列化：如果对象内部有互相引用，序列化时也要维护引用关系。
• Clone Graph（LeetCode 133）：哈希表法几乎一样的代码结构。

所以刷题的时候别只满足于 AC，可以多想一步“这题的方法还能用在哪儿”。我在刷完 138 之后，专门去做了 133（图的克隆），发现代码套路几乎同源，一次就顺了。

6. 实操中的常见问题与排查实录

6.1 random 指向 null 时的处理

这是我最开始写哈希表法时踩过的一个坑。写第二趟遍历的时候，我只判断了if cur.random:，如果不加这个判断直接写node_map[cur].random = node_map[cur.random]，当cur.random是 None 时，node_map[None]直接报 KeyError。原地复制法也有类似问题：if cur.random:不能漏，否则cur.random.next访问空指针属性会报 AttributeError。

这个细节面试官往往会专门看一眼，能写出正确的 null 处理，说明你对边界条件有意识。

6.2 链表里有环或者自引用怎么办

这道题的原始版本没有明确说链表是否有环，但实际测试中可能出现一个节点的 random 指向它自己的情况。比如node.random = node。

哈希表法在这种情况下依然正确：因为第一趟遍历已经把所有节点都创建好了，第二趟设置 random 时直接查字典就行，自引用就是node_map[cur].random = node_map[cur]，没有任何问题。

递归法也天然支持自引用：dfs 函数先把 new_node 登记到字典里，再递归处理 next 和 random，当遇到自己时直接从字典返回，不会无限递归。

原地复制法也不受影响，因为 random 处理是基于位置关系的，自引用的节点复制出来还是自引用。

6.3 原地复制法拆分时链表断开顺序

我在第一次写原地复制法的第三趟时，把链表拆断了。当时的代码是这样的错法：

while cur: copy_node = cur.next copy_node.next = copy_node.next.next cur.next = copy_node.next cur = cur.next

这个写法在复制节点不是最后一个节点时看起来没问题，但一旦 copy_node 是链表的最后一个节点，copy_node.next是 None，None.next直接报错。而且先改 copy_node.next 再改 cur.next，会丢失原链表后续节点的引用。正确顺序应该是：先保存 copy_node，再恢复原链表的 next，再检查复制节点的 next 是否存在，存在才处理复制节点的 next，最后 cur 前移。

这类错误调试起来特别费时间，因为报错的信息往往不直观。我建议你如果卡住了，把链表画在纸上，标出 cur、copy_node、cur.next 几个指针的位置变化，一眼就能看清问题出在哪。

6.4 一个隐藏最深的问题：Python 里直接赋值是深拷贝吗

这道题刷多了，有一个概念会自然冒出来：new_head = head这种赋值到底拷贝了什么？答案是只拷贝了引用，也就是浅拷贝中的“拷贝指针”，内存里还是同一个对象。所以无论如何都要显式Node(cur.val)去 new 新节点。

这个概念平时写业务代码时容易忽略，但在面试场景里，面试官喜欢让你先解释“深拷贝和浅拷贝的区别”，再说解法。如果你能先把概念讲清楚，再落到代码上，会很加分。

写在最后

随机链表的复制这道题，难度其实不算高，但它是链表类型题里“映射思维”的典型代表。哈希表法是最稳妥的答案，原地复制法最能体现功底，递归法适合用来加深对引用和延迟绑定的理解。我个人的建议是：先把哈希表法写到形成肌肉记忆，再花时间把原地复制法练熟，第三趟拆链表的细节尤其要多写几遍。等你把两种方法都在白纸上各写三遍，再去做 LeetCode 133（克隆图），你会发现整个世界都通了。这也是我刷题时最有成就感的一种体验——一道题没白刷，后面的题越刷越顺。