给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深拷贝。
示例：
image
解释： 节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。 节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。
答案
- 需要创建一个新的链表，长度和原来的链表一样
- 要想复制随机指针，只能根据对应的位置关系在新的链表上将随机指针填上
- 用一个Map将原来的链表和新的链表做一个映射
Java代码如下
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;
public Node() {}
public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public Node copyRandomList(Node head) {
Map<Node, Node> visited = new HashMap<>();
Node pPrev = null;
Node pNode = head;
// 循环一次，创建新的链表
while(pNode != null) {
Node pNew = new Node();
visited.put(pNode, pNew);
pNode = pNode.next;
}
pNode = head;
// 循环一次，在新的链表上，将随机指针给填上
while(pNode != null) {
Node pNew = visited.get(pNode);
pNew.val = pNode.val;
pNew.random = visited.get(pNode.random);
pNew.next = null;
if(pPrev != null) {
visited.get(pPrev).next = pNew;
}
pPrev = pNode;
pNode = pNode.next;
}
return visited.get(head);
}
}
