这道题使用哈希表！感觉思路非常清奇！

我们不同于以前复制简单链表那样使用双指针边动边复制，因为这个node除了存储next之外还有一个random。

因为random可以指向随便一个node，所以这道题我们需要一个快速映射所有节点的方法，那就是哈希！

我们将复制出来的节点每一个与旧节点进行映射，一一对应，那在构造新链表的next和random的时候，我们只需要使用旧链表的next和random的新链表的映射即可。

代码如下：

<div>class Solution {
    class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. 返回新链表的头节点
        return map.get(head);
    }
}</div>