type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
输入为一个长度为
n的链表的head。这个链表中的每个节点都包含一个随机指针random,该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝,返回复制链表的头节点。
这个深拷贝由
n个全新节点组成,其中每个新节点的值都等于其对应的原节点的值。新节点的
next指针和 random指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。 例如,如果原链表中有
X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。例 1:

例 2:

例 3:

解法一:哈希 + 两次遍历
这题的难点在于
random 指针。如果只按
next 顺着走,无法立即知道新链表中 “对应的随机节点” 在哪里。最自然的想法就是先把“旧节点 → 新节点”的映射存起来:
- 第一遍负责“克隆节点”(不连指针),
- 第二遍再把
next和random都接好。
这样,任何一个旧节点的
random,都能通过映射找到它的新克隆。复杂度
- 时间:
O(N)(两遍链表)
- 空间:
O(N)(哈希映射存了 N 个对应关系)
解法二:交叉拼接(最优解)
这种解法用了一个很优雅的trick :把“克隆节点”直接插在原节点后面,让链表变成
A -> A' -> B -> B' -> C -> C' ...。这样很自然地得到A' 的 random = A.random 的 next(因为 A.random 的后面就是它的克隆)。
等把所有克隆节点的
random 都设置好,再把“混合链表”拆成两份:奇数位还给原链表,偶数位就是新链表。复杂度
- 时间:
O(N)(三次线性扫描)
- 空间:
O(1)(只用少数指针变量)
解法三:递归版DFS + 哈希
把链表看作“有
next 和 random 两种边的图”。那它就是一个带可能回边的有向图。图的深拷贝思路是:
- 用哈希表记忆“旧节点 → 新节点”。
- 递归时,如果已创建过就直接返回,避免重复和死循环;否则创建新节点,再递归复制它的
next和random。
复杂度
- 时间:
O(N)(每个节点最多访问/构造一次)
- 空间:
O(N)额外映射 +O(H)递归栈(H 为“图深度”,链表视角近似O(N)最坏)
解法四:迭代版DFS + 哈希
和解法三类似,只是把递归改为手动栈,避免深递归栈溢出风险。
处理顺序:遇到旧节点就保证哈希里有对应克隆,再把它的
next、random 压栈,逐步补齐指针。复杂度
- 时间:
O(N)
- 空间:
O(N)(映射 + 栈)
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-138-随机链表的复制
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 128] 最长连续序列
下一篇
[Leetcode 143] 重排链表