138. 随机链表的复制
题目描述
输入一个长度为 n 的链表。每个节点除了 val 和 next，还有一个 random 指针，它可以指向链表中任意一个节点，也可以为空。
复制整个链表：新建 n 个节点，值与原节点一一对应。新节点的 next 和 random 只能指向新链表中的节点，且指向关系要与原链表完全对应。例如原链表里 X.random 指向 Y，那么它们的拷贝 x.random 也要指向 y。返回新链表的头节点。
输入输出中，链表写成若干个 [val, random_index] 的列表。random_index 是 random 指向的节点下标（从 0 开始），指向空时写 null。函数只接收头节点 head。
示例 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]]
解释：两个节点的 random 都指向下标 1，其中第二个指向自己。
示例 3
输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]
解释：值相同的节点也要分别拷贝，random 关系保持不变。
数据范围
0 <= n <= 1000-10^4 <= Node.val <= 10^4Node.random为空，或指向链表中的某个节点。
解题思路：哈希表映射
第一遍为每个原节点分配副本，第二遍通过映射填充 next 和 random。
为什么正确
映射中的每个原节点恰好对应一个新节点，并保留 None:None；所有副本指针都通过映射连接。
复杂度分析
时间 O(n)，额外空间 O(n)，另需 O(n) 输出节点。
易错点
138 使用题目提供的 Node 类型；random 必须指向副本，不能指回原链。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
# 使用题目提供的 Node(val) 类型，含 next、random 字段。
class Solution:
def copyRandomList(self, head):
copies = {None: None}
cur = head
while cur:
copies[cur] = Node(cur.val)
cur = cur.next
cur = head
while cur:
copies[cur].next = copies[cur.next]
copies[cur].random = copies[cur.random]
cur = cur.next
return copies[head]class Solution {
public Node copyRandomList(Node head) {
Map<Node, Node> copies = new HashMap<>();
copies.put(null, null);
Node cur = head;
while (cur != null) {
copies.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
while (cur != null) {
copies.get(cur).next = copies.get(cur.next);
copies.get(cur).random = copies.get(cur.random);
cur = cur.next;
}
return copies.get(head);
}
}class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map<Node*, Node*> copies = {{nullptr, nullptr}};
Node* cur = head;
while (cur) {
copies[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;
while (cur) {
copies[cur]->next = copies[cur->next];
copies[cur]->random = copies[cur->random];
cur = cur->next;
}
return copies[head];
}
};func copyRandomList(head *Node) *Node {
copies := map[*Node]*Node{nil: nil}
cur := head
for cur != nil {
copies[cur] = &Node{Val: cur.Val}
cur = cur.Next
}
cur = head
for cur != nil {
copies[cur].Next = copies[cur.Next]
copies[cur].Random = copies[cur.Random]
cur = cur.Next
}
return copies[head]
}var copyRandomList = function(head) {
const copies = new Map([[null, null]]);
let cur = head;
while (cur) {
copies.set(cur, new _Node(cur.val));
cur = cur.next;
}
cur = head;
while (cur) {
copies.get(cur).next = copies.get(cur.next);
copies.get(cur).random = copies.get(cur.random);
cur = cur.next;
}
return copies.get(head);
};function copyRandomList(head: _Node | null): _Node | null {
const copies = new Map<_Node | null, _Node | null>([[null, null]]);
let cur = head;
while (cur) {
copies.set(cur, new _Node(cur.val));
cur = cur.next;
}
cur = head;
while (cur) {
copies.get(cur)!.next = copies.get(cur.next)!;
copies.get(cur)!.random = copies.get(cur.random)!;
cur = cur.next;
}
return copies.get(head)!;
};其他解法
哈希表法简单不动原链表；节点拆分法省去哈希表的 O(n) 空间，但要小心地编织和拆分指针。
解法 2：节点拆分 时间 O(n)，空间 O(1)
第一遍在每个原节点后面插入它的副本，形成 A→A'→B→B'。第二遍利用相邻关系，令 A'.random = A.random.next。第三遍把交错的链表拆回原链表和副本链表。
用链表位置代替哈希表，除输出节点外只用 O(1) 额外空间。会临时修改原链表，必须在最后恢复。
class Solution:
def copyRandomList(self, head):
if not head:
return None
cur = head
while cur:
cur.next = Node(cur.val, cur.next)
cur = cur.next.next
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
new_head = head.next
cur = head
while cur:
copy = cur.next
cur.next = copy.next
copy.next = copy.next.next if copy.next else None
cur = cur.next
return new_headclass Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
for (Node cur = head; cur != null; cur = cur.next.next) {
Node copy = new Node(cur.val);
copy.next = cur.next;
cur.next = copy;
}
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; cur = cur.next) {
Node copy = cur.next;
cur.next = copy.next;
copy.next = copy.next != null ? copy.next.next : null;
}
return newHead;
}
}class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
for (Node* cur = head; cur; cur = cur->next->next) {
Node* copy = new Node(cur->val);
copy->next = cur->next;
cur->next = copy;
}
for (Node* cur = head; cur; cur = cur->next->next) {
if (cur->random) cur->next->random = cur->random->next;
}
Node* newHead = head->next;
for (Node* cur = head; cur; cur = cur->next) {
Node* copy = cur->next;
cur->next = copy->next;
copy->next = copy->next ? copy->next->next : nullptr;
}
return newHead;
}
};func copyRandomList(head *Node) *Node {
if head == nil {
return nil
}
for cur := head; cur != nil; cur = cur.Next.Next {
cur.Next = &Node{Val: cur.Val, Next: cur.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; cur = cur.Next {
cp := cur.Next
cur.Next = cp.Next
if cp.Next != nil {
cp.Next = cp.Next.Next
}
}
return newHead
}var copyRandomList = function(head) {
if (!head) return null;
for (let cur = head; cur; cur = cur.next.next) {
const copy = new _Node(cur.val);
copy.next = cur.next;
cur.next = copy;
}
for (let cur = head; cur; cur = cur.next.next) {
if (cur.random) cur.next.random = cur.random.next;
}
const newHead = head.next;
for (let cur = head; cur; cur = cur.next) {
const copy = cur.next;
cur.next = copy.next;
copy.next = copy.next ? copy.next.next : null;
}
return newHead;
};function copyRandomList(head: _Node | null): _Node | null {
if (!head) return null;
for (let cur: _Node | null = head; cur; cur = cur.next!.next) {
const copy = new _Node(cur.val);
copy.next = cur.next;
cur.next = copy;
}
for (let cur: _Node | null = head; cur; cur = cur.next!.next) {
if (cur.random) cur.next!.random = cur.random.next;
}
const newHead = head.next;
for (let cur: _Node | null = head; cur; cur = cur.next) {
const copy: _Node = cur.next!;
cur.next = copy.next;
copy.next = copy.next ? copy.next.next : null;
}
return newHead;
}