LeetCode 138.随机链表的复制 详细技术解析（含多解法）

LeetCode 138.随机链表的复制 详细技术解析含多解法在链表操作类算法题中随机链表的复制是一个经典且高频的考点其核心难点在于随机指针random的处理——随机指针可指向链表中的任意节点包括自身或空节点常规的遍历复制无法直接处理随机指针的指向容易出现指针混乱或指向原链表节点的问题。本文将从题目分析、核心难点拆解、三种主流解法哈希表法、拼接拆分法、递归法入手结合详细代码实现和示例验证彻底搞懂随机链表复制的底层逻辑适合算法进阶学习者、面试备考者阅读。本文核心亮点全程围绕题目要求严格遵循给定的Node类和Solution类格式每个解法都包含“核心思路→代码实现→步骤解析→复杂度分析”兼顾代码可运行性、逻辑严谨性和易理解性同时补充常见错误点和优化建议贴合CSDN技术博客的阅读场景。一、题目详解明确要求拆解难点1.1 题目核心要求给定一个包含随机指针的链表构造其深拷贝需满足以下3个关键条件复制链表由n个全新节点组成每个新节点的val与原节点完全一致新节点的next指针和random指针需指向复制链表中的对应节点而非原链表节点复制链表的指针关系需与原链表完全一致原链表X.random→Y复制链表x.random→y。输入输出说明输入用「[val, random_index]」表示每个节点其中random_index是随机指针指向的节点索引null表示不指向任何节点输出为复制链表的头节点最终以相同格式展示。1.2 核心难点拆解随机链表复制的核心难点的并非next指针的复制常规链表遍历即可实现而是随机指针的定位具体问题如下随机指针指向的节点可能在当前遍历节点的前方未被复制或后方已被复制无法在一次遍历中直接确定其复制节点的位置若直接复制random指针会导致复制链表的random指向原链表节点违反“深拷贝”要求空链表n0、单个节点、随机指针指向自身等边界场景需特殊处理避免空指针异常。1.3 题目示例解析帮助理解以示例1为例输入head [[7,null],[13,0],[11,4],[10,2],[1,0]]原链表共5个节点索引0~4节点0val7random指向null节点1val13random指向索引0的节点即val7的节点节点2val11random指向索引4的节点即val1的节点复制后新链表的每个节点random指针需指向新链表中对应索引的节点而非原链表节点。二、预备知识必看题目给定的Node类定义固定格式不可修改# Definition for a Node.classNode:def__init__(self,x:int,next:NodeNone,random:NodeNone):self.valint(x)self.nextnextself.randomrandomSolution类框架需实现copyRandomList方法参数为原链表头节点head返回复制链表头节点classSolution:defcopyRandomList(self,head:Optional[Node])-Optional[Node]:# 核心实现代码补充说明Optional[Node]表示head可能为None空链表解题时需优先处理该边界场景。三、三种主流解法从易到难逐步优化本文将介绍三种常用解法分别是「哈希表法最易理解」「拼接拆分法空间最优」「递归法代码简洁」每种解法都将详细拆解步骤确保新手也能看懂。3.1 解法一哈希表法空间O(n)时间O(n)最易上手3.1.1 核心思路利用哈希表字典建立「原节点→复制节点」的映射关系分两步完成复制第一次遍历遍历原链表为每个原节点创建对应的复制节点将原节点作为key、复制节点作为value存入哈希表此时仅复制val值不处理next和random指针第二次遍历再次遍历原链表通过哈希表找到每个原节点对应的复制节点依次设置复制节点的next原节点next对应的复制节点和random原节点random对应的复制节点返回哈希表中原链表头节点对应的复制节点即为复制链表的头节点。核心优势思路简单无需复杂的指针操作通过哈希表快速定位复制节点适合新手入门核心缺点需要额外的哈希表空间空间复杂度O(n)。3.1.2 代码实现# Definition for a Node.classNode:def__init__(self,x:int,next:NodeNone,random:NodeNone):self.valint(x)self.nextnextself.randomrandomclassSolution:defcopyRandomList(self,head:Optional[Node])-Optional[Node]:# 边界处理空链表直接返回Noneifnothead:returnNone# 1. 创建哈希表存储原节点与复制节点的映射关系node_map{}currhead# 第一次遍历创建复制节点仅复制val存入哈希表whilecurr:# 为每个原节点创建复制节点copy_nodeNode(curr.val)# 存入哈希表key原节点value复制节点node_map[curr]copy_node# 移动指针继续遍历currcurr.next# 2. 第二次遍历设置复制节点的next和random指针currheadwhilecurr:# 获取当前原节点对应的复制节点copy_nodenode_map[curr]# 设置next原节点的next对应的复制节点若原next为None复制next也为Nonecopy_node.nextnode_map.get(curr.next,None)# 设置random原节点的random对应的复制节点若原random为None复制random也为Nonecopy_node.randomnode_map.get(curr.random,None)# 移动指针继续遍历currcurr.next# 3. 返回复制链表的头节点原链表头节点对应的复制节点returnnode_map[head]3.1.3 步骤解析结合示例1第一次遍历原链表创建5个复制节点哈希表存储为{原节点0:复制节点0, 原节点1:复制节点1, …, 原节点4:复制节点4}第二次遍历原节点0的next是原节点1 → 复制节点0的next 复制节点1原节点0的random是None → 复制节点0的random None原节点1的next是原节点2 → 复制节点1的next 复制节点2原节点1的random是原节点0 → 复制节点1的random 复制节点0依次类推完成所有复制节点的next和random设置返回复制节点0即为复制链表的头节点与示例1输出一致。3.1.4 复杂度分析时间复杂度O(n)n为链表节点数两次遍历链表每次遍历均为O(n)哈希表的get/set操作是O(1)空间复杂度O(n)哈希表存储n个节点的映射关系额外占用O(n)空间。3.2 解法二拼接拆分法空间O(1)时间O(n)最优解法3.2.1 核心思路无需额外哈希表通过「拼接原节点与复制节点→设置复制节点的random→拆分链表」三步实现深拷贝核心是利用原链表的指针关系定位复制节点的random实现空间优化拼接阶段遍历原链表为每个原节点创建复制节点将复制节点插入到原节点和原节点的next之间即原节点→复制节点→原节点next设置random阶段再次遍历链表对于每个原节点其复制节点的random 原节点random的复制节点因拼接后原节点random的next就是其复制节点拆分阶段遍历拼接后的链表将原节点和复制节点拆分还原原链表可选题目未要求保留原链表同时提取复制节点组成新的复制链表。核心优势无需额外空间空间复杂度O(1)仅用几个指针是面试中推荐的最优解法核心缺点指针操作较复杂需注意边界处理避免链表断裂。3.2.2 代码实现# Definition for a Node.classNode:def__init__(self,x:int,next:NodeNone,random:NodeNone):self.valint(x)self.nextnextself.randomrandomclassSolution:defcopyRandomList(self,head:Optional[Node])-Optional[Node]:# 边界处理空链表直接返回Noneifnothead:returnNone# 第一步拼接原节点和复制节点原节点→复制节点→原节点nextcurrheadwhilecurr:# 创建当前原节点的复制节点copy_nodeNode(curr.val)# 保存原节点的next避免后续覆盖丢失next_nodecurr.next# 插入复制节点curr → copy_node → next_nodecurr.nextcopy_node copy_node.nextnext_node# 移动指针继续处理下一个原节点currnext_node# 第二步设置复制节点的random指针currheadwhilecurr:# 当前原节点的复制节点copy_nodecurr.next# 原节点的random可能为None若不为None复制节点的random 原random的复制节点原random.nextifcurr.random:copy_node.randomcurr.random.nextelse:copy_node.randomNone# 移动指针跳过复制节点指向 next 原节点currcurr.next.next# 第三步拆分链表提取复制节点还原原链表可选题目未要求还原原链表currhead copy_headhead.next# 复制链表的头节点第一个复制节点copy_currcopy_headwhilecurr:# 还原原节点的next原节点→原nextcurr.nextcopy_curr.next# 移动原节点指针currcurr.next# 处理复制节点的next若存在下一个复制节点更新copy_curr.nextifcurr:copy_curr.nextcurr.nextcopy_currcopy_curr.nextelse:copy_curr.nextNone# 返回复制链表的头节点returncopy_head3.2.3 步骤解析结合示例1拼接阶段原链表变为「原0→复0→原1→复1→原2→复2→原3→复3→原4→复4」设置random阶段原0的random是None → 复0的random None原1的random是原0 → 复1的random 原0.next 复0原2的random是原4 → 复2的random 原4.next 复4依次完成所有复制节点的random设置拆分阶段原链表还原为「原0→原1→原2→原3→原4」复制链表拆分为「复0→复1→复2→复3→复4」返回复0即为复制链表头节点符合示例1要求。3.2.4 复杂度分析时间复杂度O(n)n为链表节点数三次遍历链表拼接、设random、拆分每次均为O(n)空间复杂度O(1)仅使用几个指针curr、copy_curr、next_node等无额外空间开销。3.3 解法三递归法空间O(n)时间O(n)代码简洁3.3.1 核心思路利用递归的“分治思想”将链表复制拆解为「复制当前节点 递归复制next节点 递归复制random节点」同时用哈希表缓存已复制的节点避免重复复制防止循环引用如random指向自身递归终止条件当前节点为None返回None缓存判断若当前节点已复制存在于哈希表中直接返回其复制节点避免重复复制递归处理创建当前节点的复制节点存入哈希表递归复制当前节点的next节点赋值给复制节点的next递归复制当前节点的random节点赋值给复制节点的random返回当前节点的复制节点作为上一层递归的结果。核心优势代码简洁逻辑清晰适合理解递归思想核心缺点递归栈占用额外空间空间复杂度O(n)递归深度最坏为n且存在栈溢出风险n极大时。3.3.2 代码实现# Definition for a Node.classNode:def__init__(self,x:int,next:NodeNone,random:NodeNone):self.valint(x)self.nextnextself.randomrandomclassSolution:defcopyRandomList(self,head:Optional[Node])-Optional[Node]:# 哈希表缓存已复制的节点避免重复复制key原节点value复制节点self.node_map{}returnself.copy_node(head)# 递归辅助函数复制单个节点并递归复制其next和randomdefcopy_node(self,node:Optional[Node])-Optional[Node]:# 递归终止条件节点为None返回Noneifnotnode:returnNone# 若当前节点已复制直接返回复制节点避免重复复制处理random指向已复制节点的情况ifnodeinself.node_map:returnself.node_map[node]# 1. 创建当前节点的复制节点存入哈希表copy_nodeNode(node.val)self.node_map[node]copy_node# 2. 递归复制next节点赋值给copy_node.nextcopy_node.nextself.copy_node(node.next)# 3. 递归复制random节点赋值给copy_node.randomcopy_node.randomself.copy_node(node.random)# 返回当前复制节点供上一层递归使用returncopy_node3.3.3 步骤解析结合示例1调用copy_node(head)即copy_node(原0)原0未在缓存中创建复0存入缓存递归调用copy_node(原0.next原1)原1未在缓存中创建复1存入缓存递归调用copy_node(原1.next原2)依次递归直到copy_node(原4.nextNone)返回None开始回溯回溯阶段复4.nextNone递归copy_node(原4.random原0)原0已在缓存中复4.random复0继续回溯依次设置复3、复2、复1、复0的next和random最终返回复0即为复制链表头节点。3.3.4 复杂度分析时间复杂度O(n)每个节点仅被递归处理一次哈希表的查询操作是O(1)空间复杂度O(n)哈希表缓存n个节点同时递归栈的深度最坏为n链表为单链无分支总空间O(n)。四、三种解法对比面试选型参考解法时间复杂度空间复杂度优点缺点适用场景哈希表法O(n)O(n)思路简单指针操作少易理解、易实现占用额外哈希表空间新手入门、面试快速解题优先保证正确性拼接拆分法O(n)O(1)空间最优无额外开销面试加分指针操作复杂需注意边界易出错面试最优解、追求空间效率的场景递归法O(n)O(n)代码简洁逻辑清晰体现递归思想递归栈开销n极大时可能栈溢出理解递归思想、代码简洁需求场景五、示例验证三种解法均适用示例1head [[7,null],[13,0],[11,4],[10,2],[1,0]]三种解法均返回[[7,null],[13,0],[11,4],[10,2],[1,0]]与题目要求一致。示例2head [[1,1],[2,1]]原链表节点0val1random→节点1节点1val2random→节点1复制后节点0val1random→复制节点1节点1val2random→复制节点1输出[[1,1],[2,1]]。示例3head [[3,null],[3,0],[3,null]]原链表节点0val3random→null节点1val3random→节点0节点2val3random→null复制后节点0val3random→null节点1val3random→复制节点0节点2val3random→null输出[[3,null],[3,0],[3,null]]。六、常见错误点与注意事项面试避坑6.1 常见错误点错误1直接复制random指针导致复制链表的random指向原链表节点违反深拷贝要求。示例copy_node.random curr.random错误正确应为copy_node.random 复制后的节点。错误2拼接拆分法中未保存原节点的next导致链表断裂。示例直接curr.next copy_node未保存curr.next原next后续无法找到原链表的下一个节点。错误3递归法中未使用哈希表缓存导致重复复制节点出现循环引用如random指向自身时递归陷入死循环。错误4未处理空链表headNone或单个节点的边界场景导致空指针异常。6.2 注意事项面试优先选择「拼接拆分法」体现空间优化意识加分项若时间紧张可先写「哈希表法」保证正确性再优化为拼接拆分法。拼接拆分法中拆分链表时需注意最后一个节点的next处理避免空指针。递归法中哈希表需定义为类属性或全局变量确保递归过程中缓存共享。所有解法中random指针为None时需明确设置复制节点的random为None避免默认值异常。七、总结随机链表的复制核心是「解决随机指针的定位问题」三种解法各有侧重核心要点总结如下哈希表法用空间换时间通过映射关系快速定位复制节点思路简单适合入门拼接拆分法空间最优利用原链表指针关系定位复制节点指针操作复杂但面试加分递归法代码简洁体现分治思想需注意缓存和递归终止条件避免栈溢出。本题是链表操作的经典进阶题考察的核心是对链表指针的精准掌控和空间/时间复杂度的优化意识。掌握三种解法后可快速迁移到类似的链表深拷贝问题如带复杂指针的链表复制为面试和算法学习奠定基础。