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'…7next
→13next
→11next
→10next
→1next
推荐
节点交织拆分
时间
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)