hot100 随机链表的复制(138)-北京尧图网络

本题采用哈希表映射算法解决包含随机指针的特殊单链表深拷贝问题。其核心本质是建立原节点与新克隆节点间的一一映射关系通过两遍线性扫描将复杂的图状拓扑结构复制解耦为独立的“节点创建”与“引用缝合”两个阶段。当前提供的源码实现了在时间复杂度 O(N) 和额外空间复杂度 O(N) 条件下的全局最优解最终走向是完整重构出与原链表物理隔离但拓扑结构完全一致的全新链表。一、问题本质与数据模型对于普通的单链表深拷贝只需顺着next指针一路创建新节点并拼接即可。然而本题的节点引入了random指针该指针可以指向链表中的任意节点或null。这种随机指向导致链表具备了有向图的拓扑特征甚至可能包含环路。如果采用传统的单遍扫描当处理到节点 X 时其random指针可能指向后继节点 Y而此时 Y 尚未被实例化控制流将因缺乏操作对象而陷入死锁。为了解除这种前向依赖的困局算法引入了“哈希表空间映射模型MapNode, Node”。该模型将复制流程彻底拆分为两步第一步只造节点不连指针线性遍历原链表为每个原节点单独克隆一个数值相同、但处于孤立状态的新节点并记录在哈希表中Key 为原节点地址Value 为新节点地址。第二步不造节点只连指针再次遍历原链表利用哈希表作为索引桥梁跨越空间物理限制精准缝合所有新节点的next与random引用。二、算法演进对比在解决带随机指针链表的深拷贝问题时哈希表映射法在工程可读性与健壮性上具备明显的优势解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷原地拼接拆分法O(N)O(1)将克隆节点直接插入对应原节点之后形如 A - A - B - B利用相对位置设置random最后将交错的链表拆分还原不需要额外存储容器但需要多次修改原链表的拓扑结构代码逻辑较为繁琐且易出错哈希表映射法当前解法O(N)O(N)利用哈希表显式维护新旧节点的空间映射第一遍克隆节点第二遍通过哈希表缝合指针需要开辟与链表长度呈线性正比的哈希表空间内存开销随节点规模扩大而增大三、核心分支控制逻辑与决策证明当前源码的控制流由两个独立的while (cur ! null)循环串联而成其内部决策及边界处理证明如下1. 独立实体映射第一遍while循环执行map.put(cur, new Node(cur.val));数学证明原链表拥有 N 个物理节点。通过该循环哈希表中将精准存入 N 对键值对。新节点在内存中独立开辟其next和random初始均默认为null。结论完成了所有新节点实体的创建消除了后续指针缝合时“目标节点不存在”的风险。2. 拓扑关系缝合第二遍while循环执行map.get(cur).next map.get(cur.next); map.get(cur).random map.get(cur.random);决策证明由于第一步已经建立了全量映射对于任意原指针指向的节点cur.next或cur.random都可以通过map.get()在常数阶 O(1) 时间内获取其对应的克隆节点。边界证明Null 防御当原节点的指针指向null时例如尾节点的next或者某些没有随机指向的random由于哈希表中未存储null键执行map.get(null)将直接返回 Java 原生的null。结论利用map.get(null) null的底层特性算法无缝处理了链表的末梢边界与空随机指针使指针缝合逻辑实现了完全的代码归一化。四、算法执行状态机步进示例以输入链表head [[7, null], [13, 0]]为例原链表含两个节点N0 值为 7random 指向 nullN1 值为 13random 指向 N0。克隆生成的对应新节点记为 C0 和 C1。其状态演进如下表所示步骤cur 当前指向阶段与核心控制动作哈希表当前状态 (Key - Value)克隆链表当前拓扑状态1-1N0 (7)阶段一创建 C0 并存入哈希表{N0 - C0}C0 孤立存在1-2N1 (13)阶段一创建 C1 并存入哈希表{N0 - C0, N1 - C1}C0, C1 均孤立存在1-3null阶段一结束cur指针重置回head(N0){N0 - C0, N1 - C1}节点实体全量就绪准备缝合关系2-1N0 (7)阶段二缝合 C0 的next与random{N0 - C0, N1 - C1}C0.next C1;C0.random map.get(null) - null2-2N1 (13)阶段二缝合 C1 的next与random{N0 - C0, N1 - C1}C1.next map.get(null) - null;C1.random C02-3null阶段二结束触发return map.get(head);{N0 - C0, N1 - C1}最终形态C0(7)-C1(13)-null且 C1.random 指向 C0五、源码实现/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val val; this.next null; this.random null; } } */ class Solution { public Node copyRandomList(Node head) { // 创建哈希表用于存储原节点到新克隆节点的空间物理映射 MapNode, Node map new HashMap(); // 初始化工作指针 cur 指向原链表头节点 Node cur head; // 步骤 1第一遍线性扫描仅克隆节点实体并存入映射表 while (cur ! null) { map.put(cur, new Node(cur.val)); cur cur.next; } // 将工作指针重新重置回原链表头部准备进行拓扑缝合 cur head; // 步骤 2第二遍线性扫描利用映射表恢复新链表的 next 与 random 指向 while (cur ! null) { // 让新节点的 next 指针指向原后继节点对应的克隆后继 map.get(cur).next map.get(cur.next); // 让新节点的 random 指针指向原随机节点对应的克隆随机节点 map.get(cur).random map.get(cur.random); // 控制指针后移 cur cur.next; } // 从哈希表中提取并返回原头节点对应的克隆头节点 return map.get(head); } }六、复杂度分析1. 时间复杂度O(N)分析算法显式包含了两个独立的单重while循环。第一个循环遍历原链表长度 N执行 N 次哈希表插入操作第二个循环同样遍历长度 N执行 N 次哈希表查询与指针重定向操作。由于HashMap的put与get操作在平均情况下的时间复杂度均为常数阶 O(1)。结论总的计算耗时与链表的节点总数 N 呈严格的线性正比关系。2. 空间复杂度O(N)分析算法在运行全流程中构建了一个HashMap用于维系映射关系。该映射表内部存储了 N 个键值对其占用的内存空间随输入链表的节点规模线性膨胀。结论除去作为返回值所必须开辟的新链表存储空间外该算法引入的外部辅助空间复杂度为线性阶 O(N)。

hot100 随机链表的复制(138)

相关推荐

AI Agent 框架大比拼：LangChain vs LlamaIndex vs AutoGen vs CrewAI 选型指南

Free-NTFS-for-Mac 架构解析：跨平台文件系统读写的最佳实践

python神经网络编程入门（四）----神经网络误差反向传播完全图解

更多资讯

华为云部署Ward服务器监控系统实战指南

DLMS协议电表通讯详解：三层模型、HDLC帧与ASN.1编码

TDengine时序数据库WebSocket实时订阅方案设计与优化

快速排序算法实现与工程优化全解析

金融风控AI实战：从模型构建到生产部署

大模型时代数据质量管理：Rubric解决方案与实践

今日更新

AI辅助技术栈评估：提升研发决策效率60%

从生成Token到直接决策：Jev如何重塑AI Agent工程实践

32G统一内存跑大模型：内存账、TPS实测与端云分流

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？