题目：
给你一个长度为 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：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
提示：
- 0 <= n <= 1000
- -104 <= Node.val <= 104
- Node.random 为 null 或指向链表中的节点。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/copy-list-with-random-pointer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
参考【@王尼玛】大佬的题解，感谢~
哈希表：
1.创建一个哈希表，遍历原链表，遍历的同时不断创建新结点，这样将原结点作为key，新结点作为value，存储在哈希表中；
2.再一次遍历原链表，将copy的链表的next和random加上；
根据图可以看出：
map.get(原结点)：对应的新结点
map.get(原结点.next)：对应的新结点的next
map.get(原结点.random)：对应新结点的random
3.返回新链表的头结点即map.get(head)就可以了。
java代码：
1 /*
2 // Definition for a Node.
3 class Node {
4 int val;
5 Node next;
6 Node random;
7
8 public Node(int val) {
9 this.val = val;
10 this.next = null;
11 this.random = null;
12 }
13 }
14 */
15
16 class Solution {
17 public Node copyRandomList(Node head) {
18 //特判
19 if(head == null) return null;
20 //创建
21 Map<Node, Node> map = new HashMap<>();
22 //遍历原链表，并将新链表放进哈希表中
23 Node p = head;
24 while(p != null){
25 Node newNode = new Node(p.val);
26 map.put(p, newNode);
27 p = p.next;
28 }
29 //将p回到头结点
30 p = head;
31 //再一次遍历原链表，设置新链表的next和random
32 while(p != null){
33 //获取新结点
34 Node newNode = map.get(p);
35 //map.get(原结点.next)：对应的新结点的next
36 if(p.next != null){
37 newNode.next = map.get(p.next);
38 }
39 //map.get(原结点.random)：对应新结点的random
40 if(p.random != null){
41 newNode.random = map.get(p.random);
42 }
43 p = p.next;
44 }
45 //返回新链表的头结点
46 return map.get(head);
47 }
48 }
python3代码：
1 """
2 # Definition for a Node.
3 class Node:
4 def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
5 self.val = int(x)
6 self.next = next
7 self.random = random
8 """
9
10 class Solution:
11 def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
12 if not head:
13 return None
14 p = head
15 # 设一个字典,key存储原结点，value存储新结点
16 map = {}
17 while p:
18 newNode = Node(p.val)
19 map[p] = newNode
20 p = p.next
21 p = head
22 # 再次遍历原链表，设新链表设置next和random
23 while p:
24 newNode = map[p]
25 if p.next:
26 newNode.next = map[p.next]
27 if p.random:
28 newNode.random = map[p.random]
29 p = p.next
30 return map[head]
