面试桌上最常见的链表题之一就是“复制带有随机指针的链表”。这道题看起来只是把一个链表完整复制一遍可一旦动手写就会发现随机指针把“复制”变成了“结构重建”。我第一次做的时候天真地以为先按 next 顺序把节点全部 new 出来再回头连 random 就行结果写到一半卡住了新链表里每个节点的 random 到底该指向谁光凭遍历根本对应不上。这道题在 LeetCode 上对应第 138 题也是各大厂算法面经里的熟面孔。今天这篇就围绕它展开适合准备算法面试的人、正在复习链表基础的人以及实际工程里需要自己实现对象深拷贝的开发者。1. 先看清问题一条链表上多出来的 random 指针1.1 题目到底在问什么先看节点定义。一个普通的单链表节点只有 val 和 next而这道题多了一个 random 字段。random 可以指向链表中的任意一个节点也可以指向 null。复制的时候要求新链表里的每个节点val 要和原节点一致next 和 random 要分别指向“原节点对应关系在新链表里对应的新节点”。举个例子原链表 A - B - C其中 A.random CB.random nullC.random A。复制完以后新链表的 A 的 random 就必须指向 C而不是原链表的 C。也就是说random 所代表的对应关系要原样搬到新链表里去。这其实就是“深拷贝”。很多链表面试题里浅拷贝也能交差因为节点之间的逻辑关系通常就是 next 一条线走到底。但 random 让节点之间多了一堆横向引用链表从此不再是“一条线”而更像一张稀疏的图。你要复制这张图的节点同时复制节点之间的所有连线还不能把线连回旧节点上这就是题目的核心难点。1.2 为什么不能简单逐个复制最容易想到的错误解法是这样的先沿 next 遍历一遍创建所有新节点放到一个数组里然后第二遍再根据位置关系给 random 赋值。比如原链表第 2 个节点的 random 指向第 0 个节点那就让新链表第 2 个节点的 random 指向新链表第 0 个节点。这个思路看着合理问题在于random 指向的“位置”并不总是小于当前节点的下标它可以指向前面的、后面的、甚至自己而且 random 指向的是“那个节点对象”不是“下标”。在原链表里你可以通过 cur.random 直接拿到节点引用但在新链表里你手上只有一个已创建好的散落节点列表没有一张“原节点 - 新节点”的映射表。如果 random 指向的数据值恰好重复按下标处理就会错误地连到另一个值相同的节点上。打个比方这就好比你要照着同办公室的工位布置一套一模一样的工位光记住每个人的工牌号是不够的你得知道“原来坐这个人旁边的人新工位也坐在旁边”否则桌子搬过去邻座全乱了。这道题的一切解法本质上都是在解决“怎么建立并利用原节点与新节点之间的映射关系”。2. 解法一哈希表映射最符合直觉的深拷贝2.1 原理与代码实现哈希表解法非常直白先遍历原链表为每个原节点创建一个新节点然后用一张字典记录“原节点 - 新节点”的对应关系。第二遍再遍历原链表根据映射关系把新节点的 next 和 random 都接好。我用的语言是 PythonLeetCode 上已经帮你定义好了 Node 类实际做题时可以直接用class Node: def __init__(self, val0, nextNone, randomNone): self.val val self.next next self.random random def copyRandomList(head: Node) - Node: if not head: return None node_map {} cur head while cur: node_map[cur] Node(cur.val) cur cur.next cur head while cur: node_map[cur].next node_map.get(cur.next) node_map[cur].random node_map.get(cur.random) cur cur.next return node_map[head]第一遍只复制节点本身不关心指针关系。第二遍才开始接指针node_map[cur]是 cur 对应的新节点node_map.get(cur.next)是原 next 指向的原节点对应的新节点拿到之后直接赋给新节点的 next 就行。random 同理。这里特别要注意的是用get而不是[]取值。因为cur.random完全可能是 nullnull 不是字典里的合法 key用node_map.get(cur.random)时如果 random 为 nullget 会返回 None正好拿 None 当作新节点 random 的值。如果你手滑写成node_map[cur.random]LeetCode 测试用例一旦包含 random 为 null 的情况就会直接抛 KeyError。2.2 复杂度分析与面试追问时间上只遍历了两遍链表复杂度 O(n)空间上额外用了一张哈希表复杂度 O(n)。如果面试官不限制额外空间哈希表法是最稳妥的解法逻辑简单也不容易写错。面试时经常会有后续追问能不能不用哈希表做到 O(1) 额外空间这其实是在考察你对链表结构本身的使用能力。既然不能用外部映射那就只能让原节点和新节点之间产生物理上的邻居关系这就是下一节要讲的原地复制法。如果你在面试现场能先说清楚哈希表法的思路再自然过渡到原地复制面试官一般都会认为你对这个题的理解是成体系的。我个人的做题习惯是先列一个测试样例包含 random 指向自己、random 指向 null、random 互相指向三种情况然后跑一遍哈希表法确认能过再继续想优化。这样不至于一上来就在白板上画一堆箭头把自己绕晕。3. 解法二原地复制O(1) 额外空间的经典三步走3.1 第一步把复制节点插到原节点后面原地复制法的核心思路是让原节点和它的复制节点紧挨着。对原链表的每个节点 cur新建一个节点塞进 cur 和 cur.next 之间。这样原链表的节点个数直接翻倍而且有一个天然性质任意一个原节点 cur它后面紧挨着的那个新节点 cur.new就是它对应的复制节点。这一步代码在 LeetCode 上看起来短但容易写乱cur head while cur: new_node Node(cur.val, cur.next) cur.next new_node cur new_node.next循环条件要注意new_node 已经被塞到 cur 的后面了所以 cur 要跳到new_node.next而不是cur.next否则下一轮循环会误把刚建好的 new_node 当成原链表的下一节点再复制一次。这一步错的人很多写完后最好手动走一遍只有两个节点的链表确认复制节点的数量是 2 倍。3.2 第二步利用邻居关系还原 random现在原链表已经变成了“原节点 - 复制节点 - 原节点 - 复制节点”的结构。对于任意一个原节点 cur它的 random 指向某个原节点 target那么 target 的复制节点一定就在 target 的紧后面也就是cur.random.next。同时cur 的复制节点就是cur.next。所以可以直接写出最核心的一行赋值语句cur head while cur: if cur.random: cur.next.random cur.random.next cur cur.next.next这行代码为什么成立要拆开看cur.next是 cur 的复制节点cur.next.random就是这个复制节点的 random 字段cur.random是原链表上 random 指向的节点cur.random.next是那个节点对应的复制节点。于是新节点的 random 成功指向了正确的新节点。有个小细节如果cur.random本身是 null直接跳过即可新节点的 random 构造函数里默认就是 null不需要额外处理。第二个循环的步长是cur.next.next也就是每次跳过复制节点回到下一个原节点。代码里的 if 判断千万别漏一旦 cur.random 为 nullcur.random.next就会报空指针异常。3.3 第三步拆分链表并恢复原链表random 接好之后链表还是两倍长度。这一步要把两个链表拆开偶数位节点组成新链表奇数位节点恢复成原链表。拆链的关键是同时恢复原链表很多新手只拿去复制节点返回结果后原链表已经被拆得七零八落这是破坏输入数据的坏习惯。正确的代码是这样dummy Node(0) copy_cur dummy cur head while cur: nxt cur.next.next copy_node cur.next copy_cur.next copy_node copy_cur copy_node cur.next nxt cur nxt return dummy.next一步步看nxt先记住下一个原节点然后用copy_node取出当前原节点后面的复制节点。把复制节点接到新链表里之后再把cur.next恢复为nxt最后把 cur 推向下一个原节点。如果你只是想要新链表不关心原链表是否恢复确实可以把恢复那行去掉但刷题和实际工程一样都不能破坏输入。LeetCode 的测试也会校验原链表的完整性所以这一行不能省。整体额外空间只有几个指针变量不包括新建的 n 个复制节点所以额外空间是 O(1)。这里我要多说一句三步走不是背代码就能过最好在纸上画一轮链表变化。第一步结束后画每个节点后面跟一个复制节点第二步画 random 连线第三步画拆分过程。很多跟我交流过的读者都说画完这三个状态图之后这段代码的每一步循环都看得懂了。3.4 两种经典解法怎么取舍哈希表法好写好懂空间开销大一些原地复制法省空间但代码对指针操作要求高。实际工程里我反而推荐哈希表法因为你真正要维护的是代码可读性而不是省那几百字节内存。但面试时原地复制法是一个很好的加分项它能证明你理解“指针链路”而不是只会套 API。4. 解法三递归DFS复制对象图视角的通用写法4.1 思路与实现第三种写法理解起来比前两种更抽象但代码最短也更接近“深拷贝一个对象图”的通用模型。思路是复制一个节点时需要复制它的 next 和 random而复制 next 和 random 又会继续触发下一轮复制。这天然适合递归。递归版本需要一张 memo 表用来记录已经复制过的节点。否则当两个节点互相 random 指向时递归会在两个节点之间来回跳永远停不下来。代码是这样def copyRandomList(head: Node) - Node: memo {} def dfs(node): if not node: return None if node in memo: return memo[node] new_node Node(node.val) memo[node] new_node new_node.next dfs(node.next) new_node.random dfs(node.random) return new_node return dfs(head)关键点在memo[node] new_node这一行必须先执行再递归调用 next 和 random。如果先递归再登记A.random 指向 B、B.random 指向 A 时第一次访问 A 不会把 A 记入表中递归到 B 再递归回 AA 又会触发新的完整递归最终栈溢出。先登记第二次回到 A 时就能直接从 memo 里拿到已创建的新节点形成闭环。4.2 递归法的隐藏陷阱与适用场景递归法最容易被忽略的问题不是正确性而是深度。链表如果特别长比如十万个节点Python 默认递归深度上限约 1000 层直接 RecursionError。所以刷题时如果题目给的链表规模大递归法并不安全。但它有一个好处思路天然和容量无关。哈希表法是“先全部创建再统一接指针”原地复制法是“改变物理结构再拆开”递归法更像“沿着引用关系逐步展开”跟对象图的深拷贝语义完全一致。如果你之后去实现图克隆、树克隆、DOM 克隆你会发现递归版的核心骨架可以原样搬过去只是把 next 和 random 换成其他属性列表罢了。三种解法复杂度对比如下解法时间复杂度额外空间复杂度代码难度典型风险哈希表映射O(n)O(n)低注意 random 为 null 时用 get原地复制O(n)O(1)中高拆链时容易破坏原链表递归 DFSO(n)O(n)中链表过长时栈溢出面试的时候如果没有任何额外要求我首选哈希表法因为正确率高。如果面试官追问优化我就写原地复制法。如果想展示对深拷贝本质的理解再补一句“这道题本质上是在复制一张节点引用图递归法也能做到不过要防环”。这样整场回答的层次就完整了。5. 常见问题、调试技巧与场景迁移5.1 高频 Bug 与排查思路这道题的提交错误翻来覆去就那么几类。我把实际调试中最常见的问题整理成了排查表对照着检查要快得多。症状原因修复方法新链表的 random 指向原链表节点没有建立原节点与新节点之间的映射直接赋值原节点引用统一通过哈希映射或复制节点后邻居关系取新节点报 KeyError 或空指针异常random 为 null 时访问了 null.next或用字典访问了 nullrandom 为 null 时跳过赋值字典取值统一用 get()新链表 next 顺序错乱第一遍复制节点时误把复制节点当作下一轮的原节点循环推进时要跳到 new_node.next原链表被拆得七零八落拆链时只连新链表没有恢复原节点的 next 关系在拆链循环中先用临时变量保存原 next 并恢复 cur.next递归死循环或栈溢出memo 没有先登记节点链表过长先 memo 再递归或改用迭代法调试这类链表拷贝问题最有效的工具是打印链表结构。我自己会写一个辅助函数def dump(head): seen [] # 防止环导致死循环 cur head while cur and cur not in seen: seen.append(cur) random_val cur.random.val if cur.random else None print(fval{cur.val}, random_val{random_val}) cur cur.next这个函数能把你拷贝前后的链表各打一遍看看 random 指向的对象值对不对。如果打印出来的 random_val 都一致说明结构复制成功如果不一致再看是第几个节点出错能省一半时间。构造测试用例时至少覆盖四类边界空链表只有一个节点的链表且 random 指向自己两个节点互相 random 指向random 指向 null。这些用例能把上面五类 bug 都逼出来。5.2 从链表复制到对象图深拷贝这道题做完之后如果你只把它当成一个八股题背下来那收益就太小了。实际上这个题里“建立映射、复制节点、重建引用关系”的套路是所有深拷贝问题的最小公共骨架。遇到二叉树的复制只要沿着 left/right 递归就行遇到带环的图克隆要在遍历前就登记访问状态遇到复杂对象的序列化与反序列化核心也是先存储每个对象的唯一标识再从标识还原引用关系。理论上是“复制一份数据”实际上你要反复回答同一个问题副本里的引用到底指向谁。这个道理放到工程领域也一样。文件复制不只是把二进制内容搬过去权限、格式、索引、依赖配置都得一并处理缺了某样东西复制出来的文件或虚拟机常常打不开、格式不对。链表的随机指针就是这些“格式与依赖关系”的最小化抽象。理解了这道题你就理解了很多复制行为背后的共同规律被复制的不只是数据还有数据之间的结构关系。写在最后我给你一个实际做法上的建议初次接触这道题的时候三个解法我都建议亲手敲一遍。哈希表法帮你建立映射思维原地复制法帮你建立物理结构思维递归法帮你建立图遍历思维。哪怕最后面试只让你写一种前两种的思考过程也会让你在面试官的追问中从容不少。我自己带过几次算法小组凡是这题三种解法都写过一遍的人后面遇到克隆图、克隆二叉树普遍上手得特别快。刷题框住了答案但真正决定你水平的是你有没有看懂答案背后的那一张映射图。