复制带随机指针的链表
题目分析
本题考察的是如何实现复杂链表的深拷贝。每个节点除了普通的next指针外，还有一个随机指针random，随机指针可能指向链表中的任意节点或null。
解题思路与算法
要实现链表的深拷贝，需要确保复制链表中的random指针也能正确指向新链表中对应的节点，而不是原链表中的节点。
一种高效的解决方法为“三步走”算法：
P4049.随机链表的复制
Leetcode 138.随即链表的复制-原题链接
题目内容
给你一个长度为 n的链表，每个节点包含一个额外增加的随机指针 random，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random−−>Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random−−>y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val,randomindex] 表示：
- val：一个表示 Node.val 的整数。
- randomindex：随机指针指向的节点索引（范围从 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
- −104<=Node.val<=104
- Node.random 为 null或指向链表中的节点。
