随机链表的复制
给你一个长度为 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 作为传入参数。
示例 1：
codeType
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
codeType
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
codeType
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
提示：
- 0 <= n <= 1000
- -104 <= Node.val <= 104
- Node.random 为 null 或指向链表中的节点。
解法：
这题主要的点在于复制时是否需要创建新节点，可能会导致重复创建。所以可以用哈希表记录旧链表节点和新建链表节点的对应关系，从而避免重复创建。接下来只需要按照链表顺序判断当前节点以及random是否需要创建新节点以复制即可。val值的复制统一在next遍历时即可。
ts
/**
* Definition for _Node.
* class _Node {
* val: number
* next: _Node | null
* random: _Node | null
*
* constructor(val?: number, next?: _Node, random?: _Node) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* this.random = (random===undefined ? null : random)
* }
* }
*/
function copyRandomList(head: _Node | null): _Node | null {
// 深拷贝就是要重新创建节点，将基础类型的值复制过来
// next是一对一的关系，逐个遍历即可
// random是多对一的关系，可能会发生重复创建的情况
// 所以可以用哈希表来记录创建过的节点的引用，防止重复创建
let p1 = head // 遍历原链表的指针
let list = new _Node() // 头节点
let p2 = list
const map = new Map<_Node, _Node>() // { [p1节点的引用]: 对应的p2节点的引用 }
while(p1 !== null){
if(!map.has(p1)){ // 如果p1没被复制过
p2.next = new _Node()
p2.next.val = p1.val // 值的复制统一在遍历next的时候处理
p2 = p2.next
map.set(p1, p2) // 记录已经复制过的节点
}else{
p2.next = map.get(p1)
p2.next.val = p1.val
p2 = p2.next
}
// random 也进行复制
if(p1.random !== null && !map.has(p1.random)){ // p1.random未被复制过
p2.random = new _Node()
map.set(p1.random, p2.random)
}else{
p2.random = p1.random === null ? null : map.get(p1.random)
}
p1 = p1.next
}
return list.next
};