本文最后更新于33 天前,其中的信息可能已经过时,如有错误请发送邮件到big_fw@foxmail.com
🔗 复制带随机指针的链表
题目来源:138. 随机链表的复制 – 力扣(LeetCode)
📌 题目描述
给你一个长度为 n
的链表,每个节点包含一个额外增加的随机指针 random
,该指针可以指向链表中的任何节点或空节点。
要求你构造这个链表的深拷贝:
- 深拷贝应由
n
个全新节点组成,每个新节点的值等于原节点。 - 新节点的
next
和random
指针必须指向复制链表中的新节点。 - 不能指向原链表中的任何节点。
- 输入/输出以
[val, random_index]
形式表示,random_index
是目标节点的索引(0 到 n-1),若为null
表示不指向任何节点。
✅ 示例解析
示例 1:
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
解释:每个节点值复制,random 指针指向复制后链表中对应的新节点。
示例 2:
输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]
解释:节点1的random指向节点2,节点2的random也指向节点2(自身)。
示例 3:
输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]
⚠️ 提示
0 <= n <= 1000
-10⁴ <= Node.val <= 10⁴
Node.random
为null
或指向链表中的节点
💡 解法:哈希表映射法 —— O(n) 时间,O(n) 空间
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// 第一步:遍历原链表,创建新节点并建立映射
HashMap<Node, Node> map = new HashMap<>();
Node p = head;
while (p != null) {
map.put(p, new Node(p.val));
p = p.next;
}
// 第二步:再次遍历,设置新节点的 next 和 random
p = head;
while (p != null) {
Node temp = map.get(p);
temp.next = map.get(p.next); // 新节点的 next 指向对应新节点
temp.random = map.get(p.random); // 新节点的 random 指向对应新节点
p = p.next;
}
// 第三步:返回新链表头节点
return map.get(head);
}
}
📊 复杂度分析
- 时间复杂度:O(n)
- 两次遍历链表,每次 O(n),哈希表操作平均 O(1)。
- 空间复杂度:O(n) ✅
- 使用哈希表存储
n
个节点映射关系。
- 使用哈希表存储
🧩 解题思路
核心思想:两次遍历 + 哈希表建立原节点与新节点的一一映射
- 边界处理:
- 若
head == null
,直接返回null
。
- 若
- 第一次遍历 —— 创建节点并建立映射:
- 遍历原链表每个节点
p
。 - 为每个
p
创建一个新节点new Node(p.val)
。 - 存入哈希表
map.put(p, newNode)
→ 建立“旧节点 → 新节点”的映射。
- 遍历原链表每个节点
- 第二次遍历 —— 设置指针关系:
- 再次从头遍历原链表。
- 对每个原节点
p
:- 获取对应新节点
temp = map.get(p)
- 设置
temp.next = map.get(p.next)
→ 若p.next
为 null,则返回 null - 设置
temp.random = map.get(p.random)
→ 同理,支持 null
- 获取对应新节点
- 完成所有新节点的连接。
- 返回结果:
map.get(head)
即为复制链表的头节点。