复制带随机指针的链表

题目分析

本题考察的是如何实现复杂链表的深拷贝。每个节点除了普通的next指针外，还有一个随机指针random，随机指针可能指向链表中的任意节点或null。

解题思路与算法

要实现链表的深拷贝，需要确保复制链表中的random指针也能正确指向新链表中对应的节点，而不是原链表中的节点。

一种高效的解决方法为“三步走”算法：

Leetcode 138.随即链表的复制-原题链接

题目内容

给你一个长度为 $n$的链表，每个节点包含一个额外增加的随机指针 $random$，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 $n$个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 $next$ 指针和 $random$ 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 $X$ 和 $Y$ 两个节点，其中 $X.random --> Y$ 。那么在复制链表中对应的两个节点 $x$ 和 $y$ ，同样有 $x.random --> y$ 。

返回复制链表的头节点。

用一个由 $n$ 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 $[val, random_{index}]$ 表示：

• $val$：一个表示 $Node.val$ 的整数。
• $random_{index}$：随机指针指向的节点索引（范围从 $0$ 到 $n-1$）；如果不指向任何节点，则为 $null$ 。

你的代码只接受原链表的头节点 $head$ 作为传入参数。

输入描述

输入包含多行。

第一行包含一个整数 $n$，表示链表的长度。

接下来 $n$ 行，每行包含两个值，表示链表每个节点的情况：

• 第一个值为节点的整数值 val。
• 第二个值为随机指针指向节点的索引（从 $0$ 开始计数），若随机指针为 null，则用 -1 表示。

节点按输入顺序连接。

输出描述

输出共 $n$ 行，每行两个值，与输入格式相同，表示新链表中每个节点的 val 和 random 指针的索引。

样例1

输入

5
7 -1
13 0
11 4
10 2
1 0

输出

7 -1
13 0
11 4
10 2
1 0

样例2

输入

2
1 1
2 1

输出

1 1
2 1

样例3

输入

3
3 -1
3 0
3 -1

输出

3 -1
3 0
3 -1

提示

• $0 <= n <= 1000$
• $-10^4 <= Node.val <= 10^4$
• $Node.random$ 为 $null$或指向链表中的节点。