LeetCode 138. 随机链表的复制
题目描述
题意分析
给定带有
next和random两种指针的链表，创建一条全新的链表。每个原节点恰好对应一个新节点，值相同，两个指针的目标关系也要对应；副本的任何指针都不能指回原节点。
random可以指向前面的节点、后面的节点、自己或空节点，也可能有多个节点指向同一个目标。节点值允许重复，因此不能用值来识别目标，必须保留“原节点对应哪个副本”的关系。传入的是头指针，题面用下标展示随机指向只是输入输出的表示方式。返回副本头节点，空链表返回空；使用交织法临时改变原链表时，结束前还要恢复原连接。
解法：原地交织复制
核心思路
[!blue]
复制的难点不是创建相同值的节点，而是把每条旧指针的目标换成对应的新节点。交织法把这份对应关系临时存到原链表中：在每个原节点后面插入它的副本，于是对任意原节点
cur，cur.next都是唯一对应的副本。第一遍只负责创建节点并插入，暂不处理
random。因为随机目标可能在后面，如果尚未创建其副本，就无法正确连接。遍历时从刚插入副本的next走到下一个原节点，避免把副本再次复制。全部副本就位后，第二遍翻译随机指针。
cur.next是当前节点的副本，cur.random.next是随机目标的副本，因此将前者的random指向后者即可。随机目标为空时保留空；目标为自身或被多个节点共享时，也直接遵循同一对应关系。第三遍拆分两条链。先保存副本及它后面的下一个原节点，再让当前原节点跳过副本、接回原后继；副本则跳过下一个原节点、接到其副本。按从左到右的顺序拆分时，下一个原节点仍与副本相邻，因此这个位置关系仍可用于接线。所有随机指针已在第二遍连接完成，拆分不会再影响它们。
这种方法省去了额外映射表，但会临时修改原链表。后面的哈希映射法直接保存对应关系，整个复制过程不需要改变原节点。
解题步骤
- 头节点为空时直接返回空。
- 沿原链表遍历，为每个原节点创建副本并插在其后；保存原后继，继续处理下一个原节点。
- 再沿原节点遍历：随机目标非空时，令当前副本的随机指针指向目标原节点后面的副本。
- 保存新头
head.next，开始拆分。每次先记录当前副本和下一个原节点，再恢复原节点的next，并连接副本的next。- 拆分完成后返回保存的新头，原链表同时恢复原样。
代码实现
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
for (Node cur = head; cur != null; ) {
// 先为每个原节点插入紧邻副本，建立位置映射。
Node copy = new Node(cur.val);
copy.next = cur.next;
cur.next = copy;
cur = copy.next;
}
for (Node cur = head; cur != null; cur = cur.next.next) {
if (cur.random != null) {
// 随机目标原节点的后继，就是它对应的副本。
cur.next.random = cur.random.next;
}
}
Node newHead = head.next;
for (Node cur = head; cur != null; ) {
Node copy = cur.next;
// 拆分前保存下一个原节点，同时恢复原链与连接副本链。
Node nextOriginal = copy.next;
cur.next = nextOriginal;
copy.next = nextOriginal == null ? null : nextOriginal.next;
cur = nextOriginal;
}
return newHead;
}
}
func copyRandomList(head *Node) *Node {
if head == nil {
return nil
}
for cur := head; cur != nil; {
// 先为每个原节点插入紧邻副本，建立位置映射。
copyNode := &Node{Val: cur.Val, Next: cur.Next}
cur.Next = copyNode
cur = copyNode.Next
}
for cur := head; cur != nil; cur = cur.Next.Next {
if cur.Random != nil {
// 随机目标原节点的后继，就是它对应的副本。
cur.Next.Random = cur.Random.Next
}
}
newHead := head.Next
for cur := head; cur != nil; {
copyNode := cur.Next
// 拆分前保存下一个原节点，同时恢复原链与连接副本链。
nextOriginal := copyNode.Next
cur.Next = nextOriginal
if nextOriginal != nil {
copyNode.Next = nextOriginal.Next
}
cur = nextOriginal
}
return newHead
}
复杂度分析
- 时间复杂度：$O(n)$，创建、设置随机指针、拆分各遍历一次原链表，每个节点只做常数次操作。
- 空间复杂度：$O(1)$，只使用固定数量的辅助指针；深拷贝必须创建的 $n$ 个新节点属于输出空间，另计为 $O(n)$。
关键点总结
[!green]
- 先建立每个原节点到副本的对应，再按照对应关系复制指针目标。
- 交织位置临时充当映射，节点值相同也不会混淆身份。
- 随机指针全部设置完后才能拆链，拆分同时恢复原链表和连接新链表。
- 深拷贝要求连接结构一致，且两条链表的节点集合完全不相交。
补充解法：哈希表保存节点映射
核心思路
[!blue]
用哈希表直接保存“原节点 → 副本节点”。键是节点本身的引用或指针，不是节点值，这样重复值的不同节点仍然拥有各自独立的副本。
第一遍沿
next创建所有副本并登记映射；第二遍再设置指针。原节点的next指向谁，副本的next就指向那个节点对应的副本；random同理。所有副本已提前建立，所以前指、后指、自指都能直接查表，共享的目标也会映射到同一个副本。空指针没有对应节点，Java 对不存在的键调用
get得到null，Go 查找不存在的指针键得到零值nil，因此可以统一处理空孩子与空头节点。这个方法始终只读取原链表，代价是额外保存一张线性大小的映射表。
解题步骤
- 创建从原节点到副本的映射表。
- 第一遍遍历原链表，为每个节点创建同值副本，保存对应关系。
- 第二遍取出当前副本，分别查找原
next、random对应的副本并连接。- 返回原头节点映射到的副本；原头为空时自然返回空。
代码实现
class Solution {
public Node copyRandomList(Node head) {
Map<Node, Node> copies = new HashMap<>();
for (Node cur = head; cur != null; cur = cur.next) {
copies.put(cur, new Node(cur.val));
}
for (Node cur = head; cur != null; cur = cur.next) {
Node copy = copies.get(cur);
copy.next = copies.get(cur.next);
copy.random = copies.get(cur.random);
}
return copies.get(head);
}
}
func copyRandomList(head *Node) *Node {
copies := make(map[*Node]*Node)
for cur := head; cur != nil; cur = cur.Next {
copies[cur] = &Node{Val: cur.Val}
}
for cur := head; cur != nil; cur = cur.Next {
copyNode := copies[cur]
copyNode.Next = copies[cur.Next]
copyNode.Random = copies[cur.Random]
}
return copies[head]
}
复杂度分析
- 时间复杂度：$O(n)$，两次线性遍历，哈希表插入和查询平均为 $O(1)$。
- 空间复杂度：$O(n)$，映射表为每个原节点保存一条记录；副本节点占用的 $O(n)$ 输出空间另计。
关键点总结
[!green]
- 映射键必须反映节点身份，不能拿节点值代替。
- 先建立全部副本，再连接指针，避免目标副本尚不存在。
- 通过同一映射翻译
next和random，保留原图中的目标共享关系。- 原链表全程不变，与交织法的区别在于对应关系保存在哪里。
易错点总结
[!yellow]
- 直接把原节点的
random赋给副本，会让新链表指回原链表，得到的不是深拷贝。- 用节点值作为映射键，重复值的不同节点会被合并，随机指针关系随之出错。
- 插入副本后仍按普通的
cur = cur.next前进，会进入新插入节点并继续复制；应跳到保存的下一个原节点。- 副本尚未全部建立就连接随机目标，可能找不到指向后方节点的副本。
- 原随机指针为空时仍访问其
next，会触发空指针错误。- 只拆出副本而不恢复旧节点连接，会把原链表留在交织状态；两个链表的
next都要处理。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 133. 克隆图 | 中等 | 两题都必须保持原节点到副本节点的一一对应，才能复制共享引用和环；本题把映射临时存入 next，图克隆使用显式哈希表保存映射。 |