刷 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 核心思路用字典把“翻译关系”记下来哈希表法最直白思路分三步第一趟遍历顺着 next 指针走一遍原链表每遇到一个原节点就创建一个与之对应的新节点然后用一个字典把原节点 - 新节点的映射关系存下来。这一步不管 random只负责“造人”。第二趟遍历再走一遍原链表这次利用字典把每个新节点的 next 和 random 都接上。node_map[cur].next node_map[cur.next]意思是“当前原节点的下一个原节点对应到新链表里就是当前新节点的下一个新节点”。最后返回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_head3.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 是 NM.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)较短非常推荐原地复制法O(n)O(1)较长视情况推荐递归法O(n)O(n)含递归栈最短不推荐为主答时间上三种方法没有本质差别都是 O(n)因为每个节点都只被处理常数次。但空间上差别明显哈希表法和递归法需要 O(n) 的额外空间原地复制法只需要几个临时指针。5.2 面试时怎么选我的习惯是分情况。如果面试官没有做任何空间限制我直接讲哈希表法。它最好理解、最不容易写错面试官也最容易跟进你的思路。我会把两层循环的逻辑讲清楚第一层“建映射”第二层“接指针”。如果面试官追问“能不能优化空间复杂度”我再切换到原地复制法。切换的时候我会先说清楚核心技巧——“把复制节点插在原节点后面这样 random 的映射就变成了相对位置映射”然后再动手写代码。这样面试官会认为你对两种方案都有真正的理解而不是只会背答案。如果面试官进一步问“递归怎么写”我才会提递归法并且会主动说明它的递归栈空间限制。这样既展示了知识广度又体现了工程思维。5.3 从这道题迁移出去的知识点这道题的核心套路是“构建新旧节点之间的映射关系”这个思路可以迁移到很多场景图的深拷贝给一个图返回它的深拷贝本质也是新旧节点的映射。复杂对象的序列化与反序列化如果对象内部有互相引用序列化时也要维护引用关系。Clone GraphLeetCode 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是 NoneNone.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克隆图你会发现整个世界都通了。这也是我刷题时最有成就感的一种体验——一道题没白刷后面的题越刷越顺。