空间)
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, val0, nextNone, randomNone): self.val val self.next next self.random randomval 是节点值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_newkey 是原链表节点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 重新指向 Bnew.next new.next.next是让 A 重新指向 B。因为 A 的 next 原本是 BB 的 next 原本是 B所以两步操作刚好把两条链分开。5.3 拆链步骤最容易翻车我见过不少人在拆链这里写崩。常见的错误写法是先把old.next改掉再用old.next.next去找新链表的下一节点结果拿到的是旧链表的下一节点新链表穿串时全部错位。更稳的做法是拆链前先想清楚三个指针old当前旧节点初始是 headnew当前新节点初始是 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. 迭代 哈希表不用递归也能完成 DFS6.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 复杂度与适用场景对比实现方案时间复杂度额外空间是否修改原链表核心数据结构推荐场景暴力位置查找O(n²)O(n)否两个辅助数组仅用于理解题意超长链表不可用哈希表两次遍历O(n)O(n)否字典面试首选写起来最稳递归 记忆化O(n)O(n)否字典 系统栈适合讲解不适合超长链节点交织法O(n)O(1)是但可恢复无面试官追问空间复杂度时使用迭代 哈希表O(n)O(n)否字典 显式栈工程上最稳妥避免递归爆栈这个表基本能回答大多数面试追问。记住复杂度之后还有个现实问题不要一上来就写节点交织法。它虽然空间最优但三遍扫描逻辑多拆链部分容易写错写错以后 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 本质上是一个模型都是把带多条边的对象结构在新内存里重建一遍刷完这题顺手把那题也做了你会对“图深拷贝”这个概念理解得更通透。
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, val0, nextNone, randomNone): self.val val self.next next self.random randomval 是节点值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_newkey 是原链表节点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 重新指向 Bnew.next new.next.next是让 A 重新指向 B。因为 A 的 next 原本是 BB 的 next 原本是 B所以两步操作刚好把两条链分开。5.3 拆链步骤最容易翻车我见过不少人在拆链这里写崩。常见的错误写法是先把old.next改掉再用old.next.next去找新链表的下一节点结果拿到的是旧链表的下一节点新链表穿串时全部错位。更稳的做法是拆链前先想清楚三个指针old当前旧节点初始是 headnew当前新节点初始是 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. 迭代 哈希表不用递归也能完成 DFS6.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 复杂度与适用场景对比实现方案时间复杂度额外空间是否修改原链表核心数据结构推荐场景暴力位置查找O(n²)O(n)否两个辅助数组仅用于理解题意超长链表不可用哈希表两次遍历O(n)O(n)否字典面试首选写起来最稳递归 记忆化O(n)O(n)否字典 系统栈适合讲解不适合超长链节点交织法O(n)O(1)是但可恢复无面试官追问空间复杂度时使用迭代 哈希表O(n)O(n)否字典 显式栈工程上最稳妥避免递归爆栈这个表基本能回答大多数面试追问。记住复杂度之后还有个现实问题不要一上来就写节点交织法。它虽然空间最优但三遍扫描逻辑多拆链部分容易写错写错以后 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 本质上是一个模型都是把带多条边的对象结构在新内存里重建一遍刷完这题顺手把那题也做了你会对“图深拷贝”这个概念理解得更通透。
