企业官网建设流程全解析

LeetCode 138 这题，我在算法面试题单里见了不下十次，身边也有不少朋友在电面和现场面里栽在它手上。随机链表的复制，字面意思很清晰：链表节点带 val、next、random 三个字段，让你构造一份深拷贝，使新链表的所有 next 和 random 关系与原链表完全一致。难点全藏在 random 上——它不按顺序指向，可能跑到头部、尾部、中间任意节点，甚至指向 null。我第一次做这题时心想，next 能遍历，random 不也能顺着走吗？上手一写才发现，如果没有一张从旧节点到新节点的映射表，random 在新链表里根本无从定位。这篇内容我准备把五种可落地的解法全部拆开讲：暴力位置查找、哈希表两次遍历、递归记忆化、迭代 DFS，以及额外空间 O(1) 的节点交织法。每种方案都会给出完整代码、复杂度分析和实际调试中踩过的坑，无论你是在备面试，还是想彻底搞懂深拷贝，都能直接参考。

1. 题目到底在考什么：random 的深拷贝

1.1 先看原题模型

LeetCode 138 里的节点长这样：

class Node: def __init__(self, val=0, next=None, random=None): self.val = val self.next = next self.random = random

val 是节点值，next 指向下一个节点，random 指向链表中的任意一个节点，也可以指向空。题目要求返回的新链表，不能复用原链表的任何节点对象，也就是要做深拷贝。

“深拷贝”这个词看起来高级，本质就一句话：新旧链表之间不能共享同一个节点。比如新链表某个节点的 random 直接赋成了old_node.random，那它指向的就是旧链表的对象。这个操作只是复制了引用，不是复制结构，一旦新链表或旧链表发生修改，两边会互相影响。面试时只要面试官追问一句“你的新链表里有没有节点是原链表里的对象”，很多人就露馅了。

1.2 为什么“复制 next”远远不够

普通单链表复制很简单，遍历一遍原链表，每遇到一个节点就new Node(cur.val)，然后把新建节点接到前一个复制节点后面，next 关系就完整了。但 random 这条边不是顺序边，它打破了链表的“前驱后继”关系。

举个场景：原链表长度是 20，当前节点在第 5 位，它的 random 指向第 17 位节点。可你在遍历到第 5 位时，第 17 位的新副本可能还没创建。就算你强行先找，也会面临一个尴尬问题：怎么知道当前节点的 random 对应新链表里的哪个节点？如果 random 正好指向两个 val 相同的节点，难道随便选一个吗？肯定不行，链表允许相同 val 的节点存在，必须按“原节点身份”来对应。

所以这道题的核心根本不是遍历链表，而是建立“旧节点 -> 新节点”的映射关系。把这一点想透，解法就都围绕映射展开。

1.3 三种解法流派

我刷了几年题，看过的 138 解法基本可以归成三类：

• 位置映射派：先复制出主干链，同时把新旧节点分别存在数组里，再通过数组下标找到 random 对应的新节点。直观但慢。
• 哈希映射派：用字典把原节点和新节点一一对应，不管 random 指向谁，都能 O(1) 查出新节点。这是最主流的方案，又可以细分成两次遍历、递归 DFS、迭代 DFS。
• 邻接映射派：也就是节点交织法，把新节点先插到原节点旁边，形成 A-A'-B-B' 的结构，这样“旧节点.random.next”天然就是“新节点对应的 random”。不用额外空间，但代码细节多。

后面五种方案，其实就是这三条路线上的具体实现。

2. 暴力位置查找法：最直观但最不推荐

2.1 思路拆解

暴力法的思路不需要任何技巧：先把整条链表按普通单链表复制一遍，一边复制一边把旧节点按顺序放进old_nodes数组，新节点放进new_nodes数组。之后第二次遍历旧链表，对每个旧节点找到它的 random 在old_nodes数组里的下标，再把这个下标对应的new_nodes元素赋给新节点的 random。

这相当于把“引用关系”翻译成“位置关系”。因为数组下标是天然有序的，只要能确认 random 指向的是原链表第几个节点，就能在复制链里找到对应新节点。

需要注意，这种位置关系不能靠 val 判断，必须靠节点身份。如果 random 指向的节点 val 是 3，但链表里有三个 val 为 3 的节点，下标错了就全错了。

2.2 完整实现代码

def copy_random_list_brute(head): if not head: return None old_nodes = [] new_nodes = [] dummy = Node(0) tail = dummy cur = head # 第一遍：复制主干 next，同时记录新旧节点 while cur: copy = Node(cur.val) tail.next = copy tail = copy old_nodes.append(cur) new_nodes.append(copy) cur = cur.next # 第二遍：处理 random old = head new = dummy.next while old: if old.random: # 在原节点数组里定位 random 的位置 idx = next( i for i, node in enumerate(old_nodes) if node is old.random ) new.random = new_nodes[idx] old = old.next new = new.next return dummy.next

代码本身不复杂，核心就一步：node is old.random判断节点身份，不能用==。Python 的 Node 默认没重写__eq__，==也是比较对象地址，所以这里用is更明确。

2.3 复杂度和它的唯一价值

暴力法的时间复杂度是 O(n²)，因为找 random 下标时需要线性扫描old_nodes数组。如果链表有十万个节点，random 又都指向尾部节点，第二遍循环几乎等于每次都从头扫到尾部，LeetCode 上会直接超时。额外空间 O(n)，两个数组各占一份节点引用，也不算省空间。

但我面试时偶尔还是会先提一句暴力法。它的价值不是作为答案，而是作为“分析问题”的起点：你会意识到，random 无法通过遍历顺序预判，所以需要建立映射。把暴力法说清楚，再自然过渡到哈希表法，比直接背一段哈希表代码显得更真实，面试官也会觉得你确实理解了解法演进的过程。

3. 哈希表两次遍历：面试优先给的标准解

3.1 一张字典就能解决 random 定位

哈希表法是 138 最经典、也最应该优先掌握的解法。核心是维护一个字典old_to_new，key 是原链表节点，value 是新建的复制节点。

第一遍只遍历原链表，每遇到一个节点就Node(cur.val)，放进字典对应关系，不关心 next 和 random。第二遍再遍历一次原链表，利用字典把复制节点的 next 和 random 都补上。

random 的赋值写法非常直接：

old_to_new[cur].random = old_to_new[cur.random]

因为cur.random是旧链表里的一个节点，而old_to_new里已经存了它对应的新节点，所以直接查表就能拿到。整个过程不需要知道 random 在原链表的哪个位置，也不需要预判它指向什么方向。

3.2 完整实现代码

def copy_random_list_hash(head): if not head: return None old_to_new = {} # 第一遍：创建节点并建立映射 cur = head while cur: old_to_new[cur] = Node(cur.val) cur = cur.next # 第二遍：补齐 next 和 random cur = head while cur: if cur.next: old_to_new[cur].next = old_to_new[cur.next] if cur.random: old_to_new[cur].random = old_to_new[cur.random] cur = cur.next return old_to_new[head]

代码量很少，思路清晰。最后一次return old_to_new[head]直接取到新链表头节点。这里用字典以 Node 对象为 key，只要 Node 类没有重写__hash__和__eq__，对象默认按地址哈希，完全没问题。LeetCode 的 Node 类没有这些自定义，直接按上面的写即可。

3.3 两个必须避开的坑

第一，不能用Node(cur.val)创建完就顺手把next和random也复制了，而跳过第二遍。第一次创建的时候，cur.next对应的新节点可能还没创建。当然，可以通过递归或栈来“边创建边补边”，那就是后面要讲的递归版和迭代版；最稳的入门写法就是先映射、后补边。

第二，new_node.random = cur.random是绝对错误的。这会让新链表的 random 指向原链表的旧节点，破坏深拷贝要求。这也是面试里最常见的低级失误。判断是否深拷贝，就看新旧链表之间有没有共享同一个 Node 对象，有共享就是浅拷贝。

从实际刷题体验看，哈希表两次遍历是这道题的“安全牌”。时间复杂度 O(n)，空间 O(n)，不修改原链表，任何特殊情况都能处理。面试时先给出这个方案，基本不会被挑出硬伤。

4. 递归 + 记忆化：把链表复制当成图复制

4.1 从链表到图的抽象

next 和 random 可以看成每个节点最多有两条“出边”，一条指向 next，一条指向 random。如果 random 指回前面某个节点，或者多个节点的 random 互相引用，整个结构就变成一个带环的有向图，不再是一根直线。

复制链表就等价于复制这张图。从 head 出发，每遇到一个旧节点，就创建一个新节点，然后递归复制它的 next 和 random。如果某个旧节点已经创建过新节点，直接返回之前创建的，不再重复创建。

这里的关键是“记忆化”：用一个字典visited保存旧节点到新节点的映射，防止环导致无限递归。比如一个节点的 random 指向它自己，如果不做记忆化，递归会无限调用下去；做了一层判断，遇到已经创建过的节点就立刻返回。

4.2 完整实现代码

def copy_random_list_dfs(head): visited = {} def dfs(node): if not node: return None if node in visited: return visited[node] new_node = Node(node.val) visited[node] = new_node new_node.next = dfs(node.next) new_node.random = dfs(node.random) return new_node return dfs(head)

注意visited[node] = new_node这行必须放在递归 next 和 random 之前。因为当前节点的 next 或 random 可能直接或间接指回当前节点，如果先把新节点放进字典，遇到回头引用时才能拿到这个半成品；如果不先存，递归会再次为当前节点创建新副本，不仅多创建节点，还可能死循环。

4.3 递归深度的隐患

递归写法最省心，但有一个工程隐患：递归深度。

Python 默认递归深度限制大约是 1000 层，而 LeetCode 的链表长度可以到几千甚至上万。如果链表是一条长链，next 一路指向末尾，递归就会一路压栈，深度超过限制后直接抛 RecursionError。虽然可以sys.setrecursionlimit(10000)调大，但只是把天花板抬高，本质上还是在爆栈边缘试探。

面试时如果写了递归版，最好主动提一句：“这个写法在超长链下可能有递归栈风险，工程上更稳妥的是用显式栈改成迭代版。”这样既展示你懂原理，又展示你有工程意识。下一章的迭代 DFS 正是解决这个问题。

5. 节点交织法：O(1) 额外空间的进阶答案

5.1 核心思想：让旧节点身边多一个副本

哈希表好用，但面试官经常会追加一句：“能不能不用额外空间？”这时候节点交织法就该上场了。

它的核心思路很巧妙：在每个旧节点后面直接插入它的复制节点，形成交错结构。

原链表：A -> B -> C 交织后：A -> A' -> B -> B' -> C -> C'

这样做的好处非常明显。对于任意旧节点 cur，它的复制节点就是cur.next。如果cur.random指向 B，那么 B 的复制节点是B.next，也就是cur.random.next。所以设置复制节点 random 时，只需要一句：

cur.next.random = cur.random.next

不需要查字典，不需要数组，因为新旧节点的位置关系已经写死在链表结构里了。

5.2 三步走的完整实现

节点交织法分三步：插入复制节点、设置 random、拆分链表。

def copy_random_list_interleave(head): 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 # 第三步：拆分原链表和复制链表 new_head = head.next old = head new = new_head while old: old.next = old.next.next if new.next: new.next = new.next.next old = old.next new = new.next return new_head

第一步里最容易写错的是 cur 的移动。插入完 A' 后，cur 不能直接cur = cur.next，否则会走到 A'，导致重复插入。正确写法是cur = new_node.next，因为new_node.next已经指向原来的 B。

第二步结束后，原链表里每个新节点的 random 都已经指向正确的新节点。A'.random 通过A.random.next得到，B'.random 通过B.random.next得到，整体关系不会乱。

第三步是整道题最容易翻车的地方。拆链逻辑说白了就是：把奇数位置的旧节点串回原链表，把偶数位置的新节点串成新链表。old.next = old.next.next是让 A 重新指向 B，new.next = new.next.next是让 A' 重新指向 B'。因为 A' 的 next 原本是 B，B 的 next 原本是 B'，所以两步操作刚好把两条链分开。

5.3 拆链步骤最容易翻车

我见过不少人在拆链这里写崩。常见的错误写法是先把old.next改掉，再用old.next.next去找新链表的下一节点，结果拿到的是旧链表的下一节点，新链表穿串时全部错位。

更稳的做法是拆链前先想清楚三个指针：

• old：当前旧节点，初始是 head
• new：当前新节点，初始是 new_head
• 每个旧节点的下一节点必然是它对应的新节点，即old.next == new

有了这个关系，拆链的每一步就固定了：先让old.next跳过 new 回到下一个旧节点，再让new.next跳过下一个旧节点回到下一个新节点。顺序上，改old.next不影响new.next，因为new.next依然指向下一个旧节点 B，而 B 的 next 是 B'，所以可以继续用new.next = new.next.next。

节点交织法的时间复杂度是 O(n)，额外空间 O(1)。但代价是它临时修改了原始链表结构。虽然第三步会恢复原链表，但中间步骤毕竟动了旧链表。如果题目明确“原链表不可修改”，或者系统在并发读原链表，这个解法就不合适了。另外，有人担心 LeetCode 会检查原链表是否被破坏，实际上大多不检查，但作为工程习惯，恢复原链表总比不恢复更稳。

6. 迭代 + 哈希表：不用递归也能完成 DFS

6.1 显式栈替代系统栈

递归 DFS 代码漂亮，但超长链会爆栈。解决方案也不是只能靠节点交织法，可以保留哈希表思路，把递归的系统栈换成显式栈。

思路其实和递归完全一致：维护一个visited字典保存旧节点到新节点的映射，再加一个栈保存“已经创建了新节点，但还没处理完 next 和 random”的旧节点。每次从栈里弹出一个旧节点，取出对应的新节点，然后看它的 next 和 random 两条边。如果边的目标节点还没有新副本，就创建副本并压入栈；不管有没有创建，都通过字典把边连上。

这样做的本质是图的深度优先遍历，只是用显式数据结构控制遍历顺序，不再依赖 Python 的调用栈。

6.2 完整实现代码

def copy_random_list_iter_dfs(head): if not head: return None visited = {head: Node(head.val)} stack = [head] while stack: old = stack.pop() new = visited[old] if old.next: if old.next not in visited: visited[old.next] = Node(old.next.val) stack.append(old.next) new.next = visited[old.next] if old.random: if old.random not in visited: visited[old.random] = Node(old.random.val) stack.append(old.random) new.random = visited[old.random] return visited[head]

这段代码最妙的地方在于，不管 next 和 random 怎么指，都不会重复创建节点。原因很简单：每次要处理一条边之前，先检查目标旧节点是否已在visited里；不在就创建并登记，在就直接取出来用。环再复杂，所有节点也只会在第一次被遇到时创建一次。

6.3 扩展到 BFS 也没问题

显式栈版本和递归版唯一的区别是“下一个处理谁”的顺序。栈是后进先出，递归 DFS 也是后进先出，所以两者是完全等价的一种遍历。

如果你更喜欢广度优先，把stack换成collections.deque，并用popleft()替代pop()，就是标准 BFS 复制。代码其余部分完全一样。所以这一种思路可以算两种变体，笔试时按自己顺手的写就行。

从面试表达的角度看，迭代版比递归版多写几行，但能顺带解释清楚“避免递归爆栈”，是加分项。实际工程里我也更推荐这个版本，它没有递归边界的心智负担，也方便加日志调试。

7. 五种方案对比与面试实战建议

7.1 复杂度与适用场景对比

这个表基本能回答大多数面试追问。记住复杂度之后，还有个现实问题：不要一上来就写节点交织法。它虽然空间最优，但三遍扫描逻辑多，拆链部分容易写错，写错以后 debug 的时间够你重写两份哈希表了。

7.2 面试时的答题节奏

我给身边朋友的建议是分三步推进。

第一步，先简述暴力法思路，时间 O(n²)，然后立刻说“但可以优化到 O(n)”。这会让面试官看到你有分析和优化意识。

第二步，给出哈希表两次遍历，代码写在白板上，边写边解释字典作用。这是你的“保底答案”，保证正确性和可读性。

第三步，如果面试官问“能不能不用额外空间”，再上节点交织法。此时不要闷头写代码，先画一下 A-A'-B-B' 的交错结构，把三步走说清楚，再动笔。面试官看到你能画出结构，通常已经认可你的思路了。

如果面试官问递归栈风险，就切换到迭代 DFS 版本，把visited和栈的配合讲清楚。这样五种方案不是背下来的五个孤立答案，而是一条完整的推理链。

7.3 特殊用例和调试技巧

这道题的边界条件不算多，但有几个用例值得在本地自测。

空链表必须直接返回 None，五种方案都要先判空。单节点 random 指向自身，这是最容易暴露问题的用例：递归版需要visited先存节点，交织法需要cur.random.next取到自身副本，哈希表版则天然安全。random 指向最后一个节点，第一遍哈希表没有结束时，如果你用“边创建边补 next”的写法，就必须保证 random 目标的新节点已经创建，这也是为什么两次遍历哈希表最稳。

调试时我习惯写一个校验函数，检查新旧链表之间没有任何共享节点：

def nodes_set(head): result = set() while head: result.add(id(head)) head = head.next return result old_ids = nodes_set(head) new_ids = nodes_set(copy) assert old_ids.isdisjoint(new_ids)

用id(obj)拿节点地址，如果新旧集合有交集，说明有节点被复用了，深拷贝失败。这个检查在本地调试时特别有用，比肉眼盯指针高效得多。

最后再分享一下我自己练这道题的习惯：哈希表两次遍历写到闭眼能过，然后专门花时间练熟节点交织法的拆链过程。LeetCode 133 克隆图和 138 本质上是一个模型，都是把带多条边的对象结构在新内存里重建一遍，刷完这题顺手把那题也做了，你会对“图深拷贝”这个概念理解得更通透。