企业官网建设流程全解析

面试桌上最常见的链表题之一，就是“复制带有随机指针的链表”。这道题看起来只是把一个链表完整复制一遍，可一旦动手写，就会发现随机指针把“复制”变成了“结构重建”。我第一次做的时候，天真地以为先按 next 顺序把节点全部 new 出来，再回头连 random 就行，结果写到一半卡住了：新链表里每个节点的 random 到底该指向谁，光凭遍历根本对应不上。这道题在 LeetCode 上对应第 138 题，也是各大厂算法面经里的熟面孔。今天这篇就围绕它展开，适合准备算法面试的人、正在复习链表基础的人，以及实际工程里需要自己实现对象深拷贝的开发者。

1. 先看清问题：一条链表上多出来的 random 指针

1.1 题目到底在问什么

先看节点定义。一个普通的单链表节点只有 val 和 next，而这道题多了一个 random 字段。random 可以指向链表中的任意一个节点，也可以指向 null。复制的时候，要求新链表里的每个节点，val 要和原节点一致，next 和 random 要分别指向“原节点对应关系在新链表里对应的新节点”。

举个例子：原链表 A -> B -> C，其中 A.random = C，B.random = null，C.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 都接好。

我用的语言是 Python，LeetCode 上已经帮你定义好了 Node 类，实际做题时可以直接用：

class Node: def __init__(self, val=0, next=None, random=None): 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完全可能是 null，null 不是字典里的合法 key，用node_map.get(cur.random)时如果 random 为 null，get 会返回 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 为 null，cur.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 再递归回 A，A 又会触发新的完整递归，最终栈溢出。先登记，第二次回到 A 时就能直接从 memo 里拿到已创建的新节点，形成闭环。

4.2 递归法的隐藏陷阱与适用场景

递归法最容易被忽略的问题不是正确性，而是深度。链表如果特别长，比如十万个节点，Python 默认递归深度上限约 1000 层，直接 RecursionError。所以刷题时，如果题目给的链表规模大，递归法并不安全。

但它有一个好处：思路天然和容量无关。哈希表法是“先全部创建，再统一接指针”，原地复制法是“改变物理结构再拆开”，递归法更像“沿着引用关系逐步展开”，跟对象图的深拷贝语义完全一致。如果你之后去实现图克隆、树克隆、DOM 克隆，你会发现递归版的核心骨架可以原样搬过去，只是把 next 和 random 换成其他属性列表罢了。

三种解法复杂度对比如下：

面试的时候，如果没有任何额外要求，我首选哈希表法，因为正确率高。如果面试官追问优化，我就写原地复制法。如果想展示对深拷贝本质的理解，再补一句“这道题本质上是在复制一张节点引用图，递归法也能做到，不过要防环”。这样整场回答的层次就完整了。

5. 常见问题、调试技巧与场景迁移

5.1 高频 Bug 与排查思路

这道题的提交错误，翻来覆去就那么几类。我把实际调试中最常见的问题整理成了排查表，对照着检查要快得多。

调试这类链表拷贝问题，最有效的工具是打印链表结构。我自己会写一个辅助函数：

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(f"val={cur.val}, random_val={random_val}") cur = cur.next

这个函数能把你拷贝前后的链表各打一遍，看看 random 指向的对象值对不对。如果打印出来的 random_val 都一致，说明结构复制成功；如果不一致，再看是第几个节点出错，能省一半时间。

构造测试用例时，至少覆盖四类边界：空链表；只有一个节点的链表且 random 指向自己；两个节点互相 random 指向；random 指向 null。这些用例能把上面五类 bug 都逼出来。

5.2 从链表复制到对象图深拷贝

这道题做完之后，如果你只把它当成一个八股题背下来，那收益就太小了。实际上，这个题里“建立映射、复制节点、重建引用关系”的套路，是所有深拷贝问题的最小公共骨架。

遇到二叉树的复制，只要沿着 left/right 递归就行；遇到带环的图克隆，要在遍历前就登记访问状态；遇到复杂对象的序列化与反序列化，核心也是先存储每个对象的唯一标识，再从标识还原引用关系。理论上是“复制一份数据”，实际上你要反复回答同一个问题：副本里的引用，到底指向谁。

这个道理放到工程领域也一样。文件复制不只是把二进制内容搬过去，权限、格式、索引、依赖配置都得一并处理，缺了某样东西，复制出来的文件或虚拟机常常打不开、格式不对。链表的随机指针，就是这些“格式与依赖关系”的最小化抽象。理解了这道题，你就理解了很多复制行为背后的共同规律：被复制的不只是数据，还有数据之间的结构关系。

写在最后

我给你一个实际做法上的建议：初次接触这道题的时候，三个解法我都建议亲手敲一遍。哈希表法帮你建立映射思维，原地复制法帮你建立物理结构思维，递归法帮你建立图遍历思维。哪怕最后面试只让你写一种，前两种的思考过程也会让你在面试官的追问中从容不少。我自己带过几次算法小组，凡是这题三种解法都写过一遍的人，后面遇到克隆图、克隆二叉树，普遍上手得特别快。刷题框住了答案，但真正决定你水平的，是你有没有看懂答案背后的那一张映射图。