深拷贝

副标题 / 摘要 Clone Graph 不是单纯的图遍历题，而是“带环对象图的深拷贝”题。真正的关键不是能不能走完图，而是如何保证每个原节点只克隆一次，并且所有边都指向克隆图中的新节点。 预计阅读时长：12~15 分钟 标签：图、DFS、BFS、哈希表、深拷贝 SEO 关键词：克隆图, Clone Graph, 图深拷贝, LeetCode 133, DFS, BFS 元描述：通过“原节点 -> 新节点”映射表实现无向图深拷贝，讲清 DFS/BFS、环处理、复杂度与多语言代码。 目标读者 刷 LeetCode 图论题、希望掌握“深拷贝 + visited/map”模板的学习者 需要复制对象图、工作流图、拓扑结构的工程师 经常在“图遍历”和“对象复制”之间混淆的开发者 背景 / 动机 很多同学第一次做这题，会把它当成普通遍历题： DFS 一遍 BFS 一遍 把值抄过去 但真正难点在于： 图里可能有环 同一个节点可能从多条路径访问到 复制出来的新图，所有邻居必须指向“新节点”，不能混入旧节点引用 所以这题本质上是： 带环对象图的深拷贝问题 这类模式在工程里也很常见： 复制流程编排图 克隆编辑器里的节点网络 复制依赖关系图做快照 核心概念 深拷贝：返回的新图里每个节点都必须是新建对象 节点身份：判断“是不是同一个节点”看的是对象身份 / 引用，不只是 val 邻接关系保持：新图的边结构必须与原图完全一致 映射表：原节点 -> 克隆节点，既防止死循环，也防止重复创建 A — Algorithm（题目与算法） 题目重述 给定一个无向连通图中某个节点 node 的引用，请返回这个图的深拷贝。 每个节点结构如下： class Node { public int val; public List<Node> neighbors; } 题目测试用例使用邻接表表示图。 如果图不为空，给定节点总是值为 1 的节点。 ...

副标题 / 摘要 这道题的难点不是遍历链表，而是正确复制 random 指针所形成的“跨节点引用关系”。本文从朴素思路推导到哈希映射法，讲清为什么它稳定、可维护、易工程落地。 预计阅读时长：12~16 分钟 标签：链表、深拷贝、哈希表、随机指针 SEO 关键词：LeetCode 138, Copy List with Random Pointer, 随机链表复制, 深拷贝, 哈希映射 元描述：用两趟遍历 + 映射表完成随机链表深拷贝，系统讲解正确性、复杂度、工程实践与六语言实现。 目标读者 刷 LeetCode 时对 random 指针题目不够稳的开发者 想厘清“浅拷贝 vs 深拷贝”差异的同学 希望把算法思路迁移到工程对象复制场景的工程师 背景 / 动机 普通链表只要复制 val 和 next，逻辑很直观； 但随机链表多了一个 random 指针，它可能： 指向任意节点（前面、后面、自己） 也可能是 null 这使问题从“线性复制”变成“带额外引用关系的结构复制”。 工程里常见等价问题： 复制工作流节点对象，同时保留跨步骤跳转关系 复制缓存对象图，保持对象间引用一致 复制会话链，保持回溯/快捷索引引用 核心概念 浅拷贝（Shallow Copy）：只复制节点壳，内部引用仍指向旧对象 深拷贝（Deep Copy）：新建完整对象图，所有引用都指向新对象 节点身份映射：old_node -> new_node，是重建 random 的关键 结构等价：新链表应与旧链表在值与指针关系上同构，但完全不共享节点 A — Algorithm（题目与算法） 题目重述 给定一个长度为 n 的链表，每个节点有： val next random（可指向任意节点或 null） 要求构造该链表的深拷贝并返回新头节点。 新链表中的任何指针都不能指向原链表节点。 ...