LeetCode 138：随机链表的复制（Copy List with Random Pointer）深拷贝全解析
副标题 / 摘要 这道题的难点不是遍历链表，而是正确复制 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） 要求构造该链表的深拷贝并返回新头节点。 新链表中的任何指针都不能指向原链表节点。 ...