1、前言

2、思路

这道题最重要的是要构建原链表和新链表的对应关系，所以可以使用一个 hashMap，key 为原链表，value 为新链表。原链表的 next、random 找到的链表，都可以通过 hashMap 找到新链表的关系，然后按需求链接。

3、代码

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }

        Node cur = head;

        Map<Node, Node> map = new HashMap<>();
        while(cur != null){
            map.put(cur, new Node(cur.val));
            cur = cur.next;   
        }

        cur = head;
        while(cur != null){
            // 新链表 next 链接
            map.get(cur).next = map.get(cur.next);
            // 新链表 random 链接
            map.get(cur).random = map.get(cur.random);

            cur = cur.next;
        }

        return map.get(head);
    }
}