AlgoViz Lab交互式算法学习Algorithms first
随机链表的复制 · 交互式算法学习
深拷贝带 random 指针的链表。
#138 · 链表
随机链表的复制
Copy List with Random Pointer
head = [[7,null],[13,0],[11,4],[10,2],[1,0]]链表3 个关键状态
步骤 1每个副本插入原节点之后。
7→7'→13→13'…推荐
节点交织拆分
时间
O(n)空间 O(1)把副本插在原节点后面，从相邻关系推导 random，最后拆成两链。
1function copyRandomList(head) {2 for (let p = head; p;) {3 const next = p.next;4 p.next = {5 val: p.val,6 next,7 random: null8 };9 p = next;10 }11 for (let p = head; p; p = p.next.next) p.next.random = p.random?.next || null;12 const d = {13 next: null14 };15 let q = d;16 for (let p = head; p;) {17 q = q.next = p.next;18 p.next = p.next.next;19 p = p.next;20 }21 return d.next;22}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1/*2// Definition for a Node.3class Node {4 int val;5 Node next;6 Node random;7 8 public Node(int val) {9 this.val = val;10 this.next = null;11 this.random = null;12 }13}14*/15 16class Solution {17 public Node copyRandomList(Node head) {18 Map<Node, Node> d = new HashMap<>();19 Node dummy = new Node(0);20 Node tail = dummy;21 for (Node cur = head; cur != null; cur = cur.next) {22 Node node = new Node(cur.val);23 tail.next = node;24 tail = node;25 d.put(cur, node);26 }27 for (Node cur = head; cur != null; cur = cur.next) {28 d.get(cur).random = cur.random == null ? null : d.get(cur.random);29 }30 return dummy.next;31 }32}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
随机链表的复制 · 解法对比
深拷贝带 random 指针的链表。
- 测试用例
head = [[7,null],[13,0],[11,4],[10,2],[1,0]]- 题目分类
- 链表
- 解法对比
- 2
哈希映射原节点到副本
第一遍创建副本，第二遍通过映射连接 next 与 random。
- 时间
O(n)- 空间
O(n)
节点交织拆分
把副本插在原节点后面，从相邻关系推导 random，最后拆成两链。
- 时间
O(n)- 空间
O(1)
为什么有效
先建立原节点到副本节点的一一映射，再通过映射重建 next 与 random，才能保证副本完全脱离原链表。
关键不变量
第二遍连接指针前，每个原节点（以及 null）都已在映射中拥有对应副本。
易错点
- 不能让副本的 random 仍指向原节点。
- null 也应有稳定映射或显式分支。
- 节点值可能重复，映射键必须是节点引用。
边界情况
- 空链表返回 null。
- random 全为空。
- random 指向自身或前面的节点。
更多案例
[[7,null],[13,0],[11,4],[10,2],[1,0]]等价深拷贝next 与 random 都指向副本链中的节点。
[][]空链表直接返回 null。
[[1,0]][[1,0]]副本节点的 random 指向副本自身。