空间原地拼接法)
前几天有朋友跟我说他刷LeetCode刷到第138题题解看一遍觉得非常简单关上编辑器自己写却怎么都不对。这个体验我太熟悉了。随机链表的复制技术面试里考过的人基本都被它坑过尤其是被追问“能不能不用哈希表”的时候很多人当场愣住。这道题表面上是一个链表复制实际考察的是深拷贝、指针映射和引用关系的处理。只要把这道题吃透后面做图的深拷贝、复杂JSON对象的深度克隆都能用同一套思维模型。今天这篇我从零拆一遍两种主流解法都讲透附带边界用例和面试踩坑经验不管是第一次刷还是准备面试冲刺都能直接照抄。1. 一个隐藏的 random 指针为什么让复制题瞬间变难1.1 题目到底在问什么先看一下原题定义。这个链表里的节点除了val和指向下一个节点的next还有一个random指针它可以指向链表中的任意一个节点也可以指向null。要求是深度拷贝这个链表返回一个全新的链表头。所谓深拷贝就是新链表里每个节点都要在内存里真实存在不能直接复用原链表节点。光看描述很多人第一反应是这不就是遍历一遍然后new Node(val)吗问题就出在那个random上。单链表复制你只管沿着next走一路创建新节点串起来就行。但random是横向跳跃的它在原链表世界里的指向和在新链表世界里的指向不是同一个对象。你不能直接抄“旧世界”的指针地址因为新节点的地址完全不同。这就引出了这道题最核心的矛盾当你创建了一个新节点怎样在 O(1) 时间内快速找到原节点对应的那个新节点1.2 两次遍历为什么行不通最容易想到的错误方案是第一遍只复制next链暂不处理random第二遍再来补random。想象这样一个场景原链表第一个节点的random指向第五个节点。第一遍遍历时你确实把五个节点都创建出来了但遍历结束后你手里并没有一个“数组”或“映射”能告诉我“第五号原节点对应的是哪个新节点”。你只能再次扫描链表去数位置时间复杂度会退化到 O(n²)。更极端的情况是如果你不是一次性创建所有节点而是边遍历边补random那么当某个random指向的节点还没被创建出来时你根本拿不到它的指针。这个顺序问题是很多第一次手写代码的人卡住的地方。1.3 用“搬家庭地址簿”来理解我习惯用一个类比假设你有一本老房子的通讯录里面每个人的联系方式都是“住址 电话”有些人的备注还写着“他是某某某的邻居”。现在你要搬进一栋新楼新楼的房间号和旧楼完全不一样。你不能把旧通讯录里的地址原样抄到新通讯录里因为那边还没做新旧地址的对应记录。哈希表解法就相当于你随身带一张对照表上面写着“旧房间 301 对应新房间 101旧房间 302 对应新房间 102”每次照一张答案自然就出来了。而原地拼接解法更狠直接在新楼里按旧楼的门牌顺序装修房子并且把每个“邻居备注”翻译成新门牌。理解了这一点整道题的解题方向就清晰了。你要解决的从来不是“怎么创建节点”而是“新老节点怎么对应”。2. 哈希表法先建立新旧节点映射再翻译指针2.1 核心思路哈希表方案是最直接也最容易写对的解法。它不追求极致的空间优化而是用额外的 O(n) 空间换取 O(n) 时间和思路上的清晰。具体分成两步第一遍遍历原链表为每一个原节点创建一个值相同的新节点同时把“原节点 - 新节点”的对应关系存进哈希表。第二遍遍历原链表查哈希表把新节点的next和random指针都接到对应的新节点上。这里的关键点是必须先把所有节点创建出来并建立原节点到新节点的映射再去补指针。因为random可能指向链表尾部的节点如果边创建边补指针很容易遇到“目标节点还不存在”的情况。2.2 迭代版代码Python 示例class Solution: def copyRandomList(self, head: Node) - Node: 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]代码非常短但里面藏着一个容易忽略的点。第二轮设置random时要判断cur.random是否为null。如果原节点的random是null那么新节点对应的random也应该保持None。不判空直接调用.random会抛异常这是很多人第一次提交时挂掉的原因之一。2.3 递归版代码与一个容易忽略的细节除了迭代递归也可以解决而且代码看起来更贴近图的深度优先遍历。这里用memo字典记录已经创建过的克隆节点。class Solution: def copyRandomList(self, head: Node) - Node: memo {} def dfs(node): if not node: return None if node in memo: return memo[node] # 注意必须先把新节点放进 memo再去递归处理 next 和 random 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。如果不提前登记等递归到某个节点它的random反向指回前面已经创建过的节点时dfs发现自己已经处理过该节点但memo里没有记录就会继续递归陷入死循环。提前登记相当于把“正在创建中”的状态告诉系统这个原节点对应的新节点已经存在了你直接拿这个引用就行。这跟哈希表迭代版里“先建完所有节点再补指针”的逻辑是一模一样的都是为了保证节点之间的循环依赖能被正确切断。不过实际面试中如果链表长度达到几万甚至十万递归版可能会造成栈溢出所以工程上我更推荐迭代版。递归版的价值在于帮你理清“深度优先复制引用结构”的思路为后面做图的深拷贝打基础。2.4 复杂度与适用场景哈希表法的时间复杂度是 O(n)每个节点遍历两遍空间复杂度是 O(n)因为用了一张映射表。这个解法最大的优势是容易理解、不容易出错适合在面试中作为第一版答案。如果面试官追问“能不能把额外空间省掉”那就进入第三种解法了。3. 原地拼接法三次遍历空间省到 O(1)3.1 为什么能省掉哈希表原地拼接法的目标很明确不用额外的映射表而是直接利用链表本身的“物理位置”建立新老节点的对应关系。具体做法是每遍历一个原节点就在它后面紧接着插入它的克隆节点。这样处理完之后整个链表变成原节点、克隆节点交替出现原1 - 克隆1 - 原2 - 克隆2 - 原3 - 克隆3这时你会观察到一个规律任何一个原节点的next就是它的克隆节点。也就是说如果原节点 A 的random指向原节点 B那么克隆节点 A 的random应该指向的克隆节点 B恰好就是 B 的next。这就把“查找映射”变成了“指针偏移”。不需要哈希表也不需要额外查找一条random.next的路径就能直达目标。3.2 三轮遍历的完整步骤我习惯把整个过程拆成三轮每一轮只做一件事避免混在一起出错。第一轮插入克隆节点cur head while cur: clone Node(cur.val) clone.next cur.next cur.next clone cur clone.next注意循环末尾的cur clone.next。此时clone.next指向的是原来cur.next也就是下一个原节点。这个写法保证了每个原节点都被插入一个克隆节点不会漏也不会死循环。第二轮设置克隆节点的 randomcur head while cur: if cur.random: cur.next.random cur.random.next cur cur.next.next这里的cur.random是原节点的random指向的原节点cur.random.next就是它对应的克隆节点。要特别注意判断cur.random不为空否则访问.next会报错。同时循环步长是cur.next.next因为要跳过克隆节点走到下一个原节点。第三轮拆分链表dummy Node(0) tail dummy cur head while cur: tail.next cur.next tail tail.next cur.next cur.next.next cur cur.next return dummy.next第三轮比较绕。我的理解方式是dummy是克隆链表的虚拟头节点tail始终指向克隆链表的最后一个节点。每次循环把当前位置的克隆节点cur.next接到tail后面同时把原节点的next重新指回原来的下一个原节点cur.next.next恢复原链表结构。最后cur移动到下一个原节点继续。拆分完成后原链表结构被完整还原克隆链表也被完整抽出。3.3 完整代码C 版本便于对照class Solution { public: Node* copyRandomList(Node* head) { if (!head) return nullptr; // 第一轮插入克隆节点 Node* cur head; while (cur) { Node* clone new Node(cur-val); clone-next cur-next; cur-next clone; cur clone-next; } // 第二轮设置 random cur head; while (cur) { if (cur-random) { cur-next-random cur-random-next; } cur cur-next-next; } // 第三轮拆分 Node* dummy new Node(0); Node* tail dummy; cur head; while (cur) { tail-next cur-next; tail tail-next; cur-next cur-next-next; cur cur-next; } return dummy-next; } };仔细看会发现拆分时有一行容易漏掉的代码cur-next cur-next-next;。这一步的作用是还原原链表。很多初学者只记得把克隆节点摘出来却忘了把原链表的next恢复最后导致原链表被改得四不像OJ 对比结果时直接判错。3.4 为什么这种解法不会破坏原链表有同学可能会问第一轮不是把原链表插满了克隆节点吗这算不算破坏了原链表严格来说中途确实临时改变了原链表的结构但最终第三轮会完整还原。算法结束之后head指向的原链表必须和初始状态一模一样否则就不是“深拷贝”而是“边拷贝边修改原数据”了。这也是面试官考察细心程度的一个重要点。原地拼接法的时间复杂度是 O(n)三轮都是线性遍历额外空间复杂度是 O(1)除了几个指针变量和必须创建的克隆节点外没有额外存储。这在实际工程中并不多见但作为算法题它能很好地考察对链表指针操作的理解。4. 边界用例与提交后才会踩的坑4.1 容易翻车的四类测试用例这题在 LeetCode 上的用例非常全我把自己掉过的坑和它们对应的场景整理一下。用例类型可能踩的坑解决办法空链表head null直接访问head.next报空指针所有解法开头都加if not head: return None单节点且random指向自身复制后新节点的random必须指向新节点自身哈希表法查表可解原地法依赖cur.random.next同样可解random为null继续访问.random.next会报错设置指针前务必判空长链表递归解法栈溢出优先使用迭代版或原地版单节点且random指向自身是一个很容易出错的测试点。因为很多人写完代码后只验证了random为null的情况忽略自引用。实际上如果原链表只有一个节点它的random指向自己那么哈希表版里old_to_new[cur].random old_to_new[cur.random]会正确地把新节点的random指向新节点自己原地版里第二轮的cur.next.random cur.random.next由于cur.random就是curcur.random.next刚好是克隆节点自己逻辑也成立。4.2 “深拷贝”这个词的含义这道题官方标注是“深拷贝”这是很多人的第二个坑。有人可能觉得直接返回head不就行了吗反正看起来一样。绝对不行。深拷贝要求内存中重新分配一份独立的数据你不能把原节点拿过来直接复用。具体来说如果你返回的是原链表的某个指针那么修改新链表任意节点的val或random原链表也会跟着变。这属于浅拷贝不符合题意。面试时如果被问到这个点要能解释清楚两种拷贝的区别。4.3 原地法忘记还原原链表的后果原地法第三轮里cur.next cur.next.next这行看起来不起眼但删掉它OJ 会是什么表现分两种情况一种是最终返回的克隆链表dummy.next本身没问题因为克隆节点的指针已经被正确抽取并串联了。但原链表结构被破坏了所有原节点的next仍然指向克隆节点而不是恢复成原来的顺序。如果判题系统在函数返回后再去检查原链表内容或者下一组测试用例复用同一片内存错误就会暴露出来。另一种更隐蔽的问题是如果原链表的random指向的节点位置在链表中间而克隆节点占据了原来next的位置后续再次遍历时可能会把克隆节点当作原节点导致结果错乱。所以记住第三轮不仅要“抽”克隆链还要“还原”原链两步缺一不可。4.4 两种解法的对比与选择维度哈希表法原地拼接法时间复杂度O(n)O(n)额外空间O(n)O(1)实现难度低思路直接中高三轮指针操作易混出错点判空、映射方向拆分顺序、忘记还原原链面试价值保底方案快速写对展示空间优化能力我的经验是面试时先写哈希表法代码短、逻辑清晰写完通过后主动提一句“如果限制不能用额外空间我还可以用原地拼接法做到 O(1) 额外空间”。这一句话就能拉开和普通候选人的差距。5. 从这道题能迁移出去的通用解题模型5.1 图的深拷贝Clone Graph 是同门兄弟如果你刷过 LeetCode 133克隆图你会发现它的解法和哈希表版随机链表复制几乎一模一样。图中每个节点有val和一个邻居列表邻居就是random的“多版本”。解法同样是先建立“原节点 - 克隆节点”的映射再遍历节点把邻居指针复制过去。当时我把两道题放在同一天刷感觉非常强烈。它们背后的模型是同一个处理带引用关系的数据结构的深拷贝时核心永远是一个“原对象到新对象”的映射表再加上一次遍历复制边/指针。哈希表只是这个模型的通用实现工具。5.2 工程中的复杂对象深拷贝工程里也有类似场景。比如前端在状态管理库里经常要深拷贝一个带循环引用的配置对象。用JSON.parse(JSON.stringify(obj))遇到循环引用会直接报错因为 JSON 不支持环。这时候就需要一张映射表用“弱引用”字典比如WeakMap来记录“原对象 - 克隆对象”然后递归遍历对象属性遇到循环引用直接查表返回已有克隆。这和随机链表复制的哈希表思路是同一个道理。区别只是链表只有next和random两个指针而对象可能有任意多个属性。掌握这道题后再看那些复杂对象的深拷贝工具源码你会觉得亲切很多。5.3 面试时可展示的思维过程面试官问你“请实现随机链表的复制”时理想的思考路径是这样的先口头复述题目和面试官确认深拷贝的定义新节点不能复用原节点。给出暴力思路先复制 next 再补 random但需要 O(n²) 扫描指出不可接受。提出优化方向需要一种快速“由原节点找新节点”的方式于是想到哈希表。写出哈希表版并解释每一轮的职责。面试官追问能否优化空间时再提出原地拼接法画出交替链表的结构说明三轮遍历各自的职责。这套路径每一步都有依据不是硬背答案面试官一听就知道你真的理解了解题过程。如果直接甩代码出来反而容易让人觉得你是背题。5.4 刷题顺序建议我建议第一次刷这道题的人把三个版本都亲手写一遍迭代哈希表版、递归哈希表版、原地拼接版。写完之后再合上编辑器从零开始在纸上写一遍原地版的三轮循环。第一轮走位是cur clone.next第二轮步长是cur.next.next第三轮注意cur.next cur.next.next。这三行代码是最容易乱的地方。手撕三遍之后基本能形成肌肉记忆。如果只记一句话就记住这道题难的不是拷贝而是建立新老节点的对应关系。对应关系一旦建立所有指针都是翻译工作。最后再分享一个小技巧。我平时写链表题习惯在每个解法里额外写一个辅助函数printList(head)用来打印链表的next走向和random指向。调试这道题时尤其有用因为光靠肉眼盯代码很难发现哪一轮漏了步长。把每一次循环后的链表结构打印出来对照原链表看一遍哪里断了、哪里错位了一目了然。面试现场没法写调试辅助函数但这个习惯能帮你在平时练习时大大缩短理解时间。
