如果你刷过LeetCode热门100题或者最近在集中准备算法面试大概率会在题单里撞见这道#138 随机链表的复制。我第一次做它是在模拟面试现场心里想的是“复制个链表谁不会new一个新节点、把next串起来不就行了”结果写了一半突然卡住——每个节点除了next之外还挂着一个random指针它指向的旧节点我根本没复制过那在新链表里它到底该指向谁这道题能进热门题单不是没道理的。它用一个很小的结构改造把“普通链表复制”升级成了“带随机索引的结构复制”同时考察了深拷贝的理解、引用操作能力和空间复杂度优化的意识。本文我会把完整解法拆开讲五种实现方案从最直白的哈希表法到空间O(1)的节点交织法每版的思路、代码和踩坑点都会讲清楚。1. 先别急着写代码这道题到底在考什么1.1 读懂题目Node 里多了一个 random 指针这道题的定义比普通链表多一个字段。LeetCode 官方给的节点结构长这样class Node { int val; Node next; Node random; public Node(int val) { this.val val; this.next null; this.random null; } }val 是节点的值next 指向下一个节点这都好理解。关键是 random 指针——它可能指向链表中的任意一个节点也可能指向 null。需要做的事情是给定一个这样的链表的头节点 head构造并返回这个链表的深拷贝。也就是说新链表的每个节点都要单独 new 出来val 和原链表一致next 结构一致random 指向的对应关系也要一致。举个例子原链表是 A → B → CA.random 指向 C那么复制出来的新链表 A → B → C 也必须满足 A.random 指向 C。这里 C 是 C 的新副本而不是 C 本身。1.2 为什么它能进“热门100题”表面看这是一道链表操作题实际上它是“图结构克隆”的一个简化版。每个节点有两条出边next 和 random。如果只顺着 next 走random 会把你带到任意位置这就不再是一条普通的一维链表了。面试官喜欢这道题主要有三个原因它能快速检验你是否理解“深拷贝”——很多候选人上来就Node newHead head这不是复制链表只是复制了一个指针。它考察哈希表在“旧对象—新对象”映射中的典型用法这是工程里非常常见的设计模式。它有一个空间 O(1) 的进阶解法节点交织法适合做追问和压力测试考察候选人有没有优化意识。类似的题还有克隆图#133、复制带随机指针的二叉树思路是相通的。刷透这一道等于把这类“结构复制”的题都串起来了。1.3 深拷贝不是浅拷贝理解错了全盘皆输很多人在这一步就开始翻车。深拷贝要求新旧两个链表完全独立不能共享任何一个节点。浅拷贝是什么概念相当于你买了一本书然后把书的封面撕下来复印了一张盖上去里面的每一页还是原来那本。旧链表改一个节点的值新链表“跟着变”因为共享了内存。深拷贝则相当于重新抄写一整本书每一个字、每一页的顺序、每一处批注的位置都独立重建。抄完之后两本书互不影响改一本不会动到另一本。这道题要的就是后者。如果你只是把 Node 的 val 逐一遍历复制但 random 直接指向原链表的节点那新旧链表就纠缠在一起了测试用例一验证就会报错。所以真正的难点在于如何在创建新节点的同时建立“旧 random 指向 → 新 random 指向”的正确映射。2. 五种方案怎么选空间换时间还是原地腾挪2.1 哈希系方案为什么直觉都是先建映射随机链表的 random 指针最大的麻烦在于你复制到第 3 个节点时它的 random 可能指向第 100 个节点而第 100 个节点的副本还没创建。就算你已经创建了怎么在新链表里找到对应的副本遍历找每次 O(n)整体 O(n²)太慢。哈希表就是用来解决“旧节点到新节点对应关系”的。第一次遍历时把每个旧节点作为 key对应新建的节点作为 value 存进 Map之后无论 random 指向哪里都能 O(1) 找到它的新副本。这是最符合直觉的思路也是绝大多数人最先想到的方案。2.2 图视角方案DFS 和 BFS 为什么也成立如果把 random 也看成一条边那么每个节点最多有两条出边整个“链表”其实是一个有向图。图怎么复制经典做法是 DFS 或 BFS 遍历原图每遇到一个旧节点就为它创建对应的新节点并用哈希表记录映射。遇到一条边比如从 A 指向 B就在新节点之间建立同样的连接。因为 random 可能形成环——比如 A.random 指向 BB.random 又指向 A——所以必须用记忆化。已经创建过副本的节点直接从哈希表取而不是再递归一次。这个思路放在这道题里完全成立代码也很简洁。2.3 原地方案节点交织法凭什么省空间哈希表把空间复杂度拉到了 O(n)。面试官追问“能不能不用额外空间”时节点交织法就登场了。核心思路非常巧妙把每个新节点直接插在对应的旧节点后面形成“旧、新、旧、新”交替的链表。这样新节点不需要哈希表也能找到“自己的位置”——原节点 x 的副本就是 x.next。更妙的是 random 的处理。原节点 x.random 指向 y那么 x.next也就是 x 的副本的 random 应该指向 y.next也就是 y 的副本。这是因为 y 的副本在穿插后就紧跟在 y 后面天然就是 y.next。这个“相邻性”让 random 的复制可以原地完成不需要任何辅助结构。它的代价是原链表结构被暂时改写了。所以最后还要做一次拆分把原链表恢复原状同时分离出新链表。2.4 复杂度速查表方案时间复杂度额外空间是否修改原链表上手难度哈希表两步法O(n)O(n)否低哈希表一步法O(n)O(n)否低DFS 递归 哈希表O(n)O(n)含递归栈否中BFS 队列 哈希表O(n)O(n)含队列否中节点交织法O(n)O(1)是需恢复中高时间上所有方案都是 O(n)差别主要在空间和代码清晰度。面试时怎么选取决于你和面试官聊到哪里。3. 五种实现逐行拆解代码细节与踩坑点3.1 方案一哈希表两步法这个方案分两遍遍历第一遍从头到尾遍历原链表只做一件事为每个旧节点 new 一个 val 相同的新节点把对应关系放进哈希表。第二遍再次从 head 出发这次用哈希表把新节点的 next 和 random 补上。public Node copyRandomList(Node head) { if (head null) { return null; } MapNode, Node map new HashMap(); // 第一遍创建所有新节点建立旧节点到新节点的映射 Node cur head; while (cur ! null) { map.put(cur, new Node(cur.val)); cur cur.next; } // 第二遍连接新节点的 next 和 random cur head; while (cur ! null) { map.get(cur).next map.get(cur.next); map.get(cur).random map.get(cur.random); cur cur.next; } return map.get(head); }这里有个很实用的小细节map.get(null)在 Java 里返回 null。所以当cur.next是 null 时map.get(cur.next)自动得到 null天然就是新链表末尾节点的 next不需要额外写if (cur.next ! null)的判断。Python 版本更简洁用dict.get()同样的道理def copyRandomList(self, head): if not head: return None d {} cur head while cur: d[cur] Node(cur.val) cur cur.next cur head while cur: d[cur].next d.get(cur.next) d[cur].random d.get(cur.random) cur cur.next return d[head]这个方案的时间是 O(n)空间是 O(n)。坏处是需要额外一个哈希表好处是思路极清晰几乎不可能写错。如果面试没有空间要求我建议直接用这个。3.2 方案二哈希表一步法两步法的缺点是遍历了两遍。能不能一遍就搞定可以前提是遇到 random 指向的节点还没创建副本时现场创建。public Node copyRandomList(Node head) { if (head null) { return null; } MapNode, Node map new HashMap(); Node cur head; while (cur ! null) { // 确保当前节点的副本存在 if (!map.containsKey(cur)) { map.put(cur, new Node(cur.val)); } // 处理 next 的副本并连接 if (cur.next ! null !map.containsKey(cur.next)) { map.put(cur.next, new Node(cur.next.val)); } map.get(cur).next map.get(cur.next); // 处理 random 的副本并连接 if (cur.random ! null !map.containsKey(cur.random)) { map.put(cur.random, new Node(cur.random.val)); } map.get(cur).random map.get(cur.random); cur cur.next; } return map.get(head); }这个写法核心就一句话要用一个映射之前先确保它存在。因为 random 可能指向链表中任意位置的节点而那个节点可能还没来得及被遍历到所以要在用到的时候“顺手”创建。一步法的优点是一遍跑完逻辑紧凑缺点是代码里 containsKey 和 get 混在一起可读性稍差面试时容易写乱。另外从性能角度看它和两步法都是 O(n)并没有本质差别。我更推荐把两步法当作主方案一步法作为“有没有更紧凑写法”的讨论话题。3.3 方案三DFS 递归 哈希表前面说过这道题可以理解为图的克隆。图论里的经典做法是带记忆化的 DFS 递归。递归函数要做三件事判断节点是否为空检查哈希表里有没有当前节点的副本没有就创建副本先存进哈希表再递归复制 next 和 random。class Solution { private MapNode, Node visited new HashMap(); public Node copyRandomList(Node head) { if (head null) { return null; } // 已经复制过直接返回缓存 if (visited.containsKey(head)) { return visited.get(head); } Node copy new Node(head.val); // 先存进哈希表再递归这一步很重要 visited.put(head, copy); copy.next copyRandomList(head.next); copy.random copyRandomList(head.random); return copy; } }很多人第一次写这个递归会把visited.put(head, copy)写在递归调用之后。这样在 random 成环的用例里会出问题假设 A.random 指向 A 自己第一次调用 copy(A)递归 copy(A.random) 又进入 copy(A)这时候哈希表里还没有 A 的记录于是又 new 了一个新节点无限递归下去直接栈溢出。先 put 再递归等于给这个节点贴了一个“正在处理中”的标签。之后再碰到它直接从缓存取递归就安全了。这个方案的代码很漂亮但要注意链表太长时递归深度可能过大工程上会有栈溢出的风险。面试时提它可以展示你对图遍历的理解但运行时稳定性不如迭代法。3.4 方案四BFS 队列 哈希表DFS 是从一个节点一路深入BFS 则是按层扩散。用队列来做图的广度优先遍历同样需要一个 visited 哈希表负责“旧节点 → 新节点”的映射。public Node copyRandomList(Node head) { if (head null) { return null; } MapNode, Node visited new HashMap(); QueueNode queue new LinkedList(); visited.put(head, new Node(head.val)); queue.offer(head); while (!queue.isEmpty()) { Node cur queue.poll(); Node copy visited.get(cur); // 复制 next 指针 if (cur.next ! null) { if (!visited.containsKey(cur.next)) { visited.put(cur.next, new Node(cur.next.val)); queue.offer(cur.next); } copy.next visited.get(cur.next); } // 复制 random 指针 if (cur.random ! null) { if (!visited.containsKey(cur.random)) { visited.put(cur.random, new Node(cur.random.val)); queue.offer(cur.random); } copy.random visited.get(cur.random); } } return visited.get(head); }这里的关键点是入队前必须判重。因为同一个节点既可能被某个节点的 next 指到也可能被另一个节点的 random 指到。如果不判重一个节点可能被多次 offer 进队列虽然最后结果大概率还是对的但会白白多做很多次操作而且在极端环状结构下可能死循环。BFS 方案不是这道题最常用的解但如果你平时刷过图的题会觉得很自然。面试中出现图类追问时把它亮出来能加分。3.5 方案五节点交织法空间 O(1) 的最优解终于到重点了。节点交织法也叫穿插复制法是这道题在空间上最优雅的解法额外空间 O(1)前提是不计递归栈。整个过程分三遍第一遍在每一个原节点后面插入它的副本形成一个交织链表。原链表 A → B → C 变成 A → A → B → B → C → C。第二遍处理副本节点的 random。因为每个原节点 x 的副本就是 x.next而 x.random 指向的节点 y 的副本是 y.next所以可以直接写cur.next.random cur.random.next。第三遍把交织链表拆成两个独立的链表同时恢复原链表的原始结构。public Node copyRandomList(Node head) { if (head null) { return null; } // 第一遍在原节点后面插入副本节点 Node cur head; while (cur ! null) { Node copy new Node(cur.val); copy.next cur.next; cur.next copy; cur copy.next; } // 第二遍设置副本节点的 random cur head; while (cur ! null) { if (cur.random ! null) { cur.next.random cur.random.next; } cur cur.next.next; } // 第三遍拆成两个链表并恢复原链表 Node dummy new Node(0); Node copyCur dummy; cur head; while (cur ! null) { Node nextCur cur.next.next; copyCur.next cur.next; copyCur copyCur.next; cur.next nextCur; cur nextCur; } return dummy.next; }第三遍拆分是很多人写错的地方。注意我在进入循环时先保存了nextCur cur.next.next这个操作很关键。如果不先保存当你执行cur.next nextCur之后原节点的新 next 已经被改掉了但你还没把副本节点挂到 copyCur 上副本节点就会丢。正确顺序是先让 copyCur 指向当前副本再恢复原节点的 next最后整体往后移动。再说一个很多教程没强调的点拆分完成后原链表必须恢复原状。因为第一遍和第二遍已经改写了原链表的 next 指向如果不恢复原链表的结构就坏了。虽然某些 LeetCode 测试用例不校验原链表是否完好但面试官一定会问“原链表被你改成什么样了”这是区分优秀解和普通解的重要细节。4. 面试场上一定会踩的坑错误写法与排查实录4.1 高频错误清单我把这些年见到过的翻车现场整理了一下基本集中在下面几个点错误现象根本原因正确处理程序报 NullPointerException第二遍处理 random 时没判断cur.random null先判空再取cur.random.next或者像哈希表法那样用map.get(null)兜底返回结果和原链表共享节点直接把 head 或原节点赋给了新链表每个节点都必须new Node(...)不能复用原对象递归陷入死循环random 成环时递归前没有把副本先放入哈希表先visited.put(head, copy)再递归BFS 队列出现大量重复节点入队前没有判断是否已访问只在!visited.containsKey(...)时才 offer交织法拆分后链表乱掉拆第三步时没有先保存cur.next.next导致副本丢失用一个临时变量先保存后继再移动指针交织法处理 random 时空指针random 指向 null 时仍执行.next操作先判断cur.random ! null4.2 用测试用例自测别只跑官方的例子很多人刷题测试只跑题解里给的简单用例一遍过了就欢呼结果面试官随便构造一个边界就露馅。我会在本地额外验证这几个用例第一个是空链表。head 为 null所有方案都应该直接返回 null这个最简单但不写代码的人反而容易在边界上出问题。第二个是单节点且 random 指向自身。head.next 为 nullhead.random head。这能检验你的实现能否处理“自己指向自己”的环。用上面的哈希表两步法第一遍创建映射后第二遍map.get(cur).random map.get(cur.random)得到的还是同一个副本节点没问题。用交织法时第二遍cur.next.random cur.random.next此时cur.random cur所以cur.random.next就是刚才插入的副本也能正确匹配。第三个是两个节点互相 random。A.random 指向 BB.random 指向 A。这能检验两个节点之间的循环引用会不会导致递归方案栈溢出。DFS 方案如果忘记先 put 缓存这个用例直接挂掉。第四个是 random 形成一条链比如 A.random → BB.random → CC.random → A。这会把图克隆的特性完全暴露出来也是递归方案最容易出问题的地方。在本地手动构造这些用例跑一遍比盲目刷十道题都有用。4.3 面试沟通技巧先聊思路再写代码这道题在面试里特别考验沟通。我的建议是不要一上来就闷头写节点交织法。哪怕你最优解已经背得滚瓜烂熟也应该先和面试官对齐思路。比较推荐的节奏是先花一两句话说明白题目的难点“因为 random 可能指向还没有创建的节点所以必须先建立旧节点到新节点的映射关系。”然后给出最简单的哈希表两步法把框架写对。写完以后主动提一句“这个方案空间是 O(n)。如果希望把额外空间压缩到 O(1)可以用穿插复制法把新节点插在原节点后面借助相邻关系处理 random最后再拆开。”大多数面试官听到这里都会顺着你的节奏往下追问。这里有个小技巧哪怕你时间不够写交织法的完整代码也一定要能把这个过程口头描述清楚并且画出穿插后的链表形态。面试官想考察的就是“你知不知道空间 O(1) 这条路”。最忌讳的是一开始就写交叉法写到一半卡在拆分步骤最后连一个能跑的版本都没交出来。面试的时候正确但平庸的答案永远好过装酷但失败的答案。5. 复杂度对照与实战建议5.1 终版复杂度对照表再贴一次完整对照表这次把容易混淆的点标注清楚方案时间空间是否破坏原链表适合场景哈希表两步法O(n)O(n)否面试首选清晰稳定哈希表一步法O(n)O(n)否代码压缩练习DFS 递归 哈希表O(n)O(n)含递归栈深度否展示图论理解BFS 队列 哈希表O(n)O(n)含队列占用否图遍历视角的补充节点交织法O(n)O(1)是但最终恢复空间敏感或面试官追问优化注意 DFS 的“空间 O(n)”是哈希表加递归栈的总和。如果原链表有 10 万个节点递归方案在工程上是有真实风险的。面试官如果问“工程上你选哪个”我的回答是默认哈希表两步法简单、可维护、不容易出边界错误只有明确要求 O(1) 空间时才上交织法。5.2 我的实战建议刷这道题我不建议只背一个最优解。正确的练习顺序应该是先用哈希表两步法把逻辑想透这一步能保证你面试时“有底”再手动从零推导交织法的三遍过程重点画出穿插后的链表形态确保每一行的指针移动都跟得上。我自己的体会是交织法第一次手写几乎必错错的地方集中在拆分步骤丢节点、乱序、忘记恢复原链表翻车概率很高。想真正掌握它就花半小时把插入、设置 random、拆分这三遍过程在白纸上完整画一遍画完再写代码比盯着答案抄五遍都有用。最后再分享一个小技巧如果你面试用的语言是 Python哈希表两步法的代码量会非常短d.get(cur.next)这种写法既简洁又能自动处理 null属于性价比极高的解法。Java 的话记住map.get(null)返回 null 这个特性也能省掉一多半的判空分支。这个题后续完全可以延伸到克隆图、复制带随机指针的二叉树这类问题上。核心方法论只有一个旧对象和新对象之间建立明确的映射关系剩下的事情都是细节。把 #138 吃透等于把整类“结构复制”的题型都拿下了。