方法一：使用Map存储

map里面key存原结点，value存新结点
时间：O(n) 空间：O(n)

class Solution {
    public ListNode copyRandomList(ListNode head) {
        ListNode cur = head;
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        // 我们用原结点作为key,新结点作为value
        Map<ListNode,ListNode> map = new HashMap<>();
        while(cur != null){
            pre.next = new ListNode(cur.val);
            map.put(cur,pre.next);
            cur = cur.next;
            pre = pre.next;
        }
        cur = head;
        pre = dummy.next;
        while(cur != null){
            pre.random = map.get(cur.random);
            pre = pre.next;
            cur = cur.next;
        }
        return dummy.next;
    }
}

方法二：

把新结点插入到原结点的后面,这个然后调整random指针，p.next.random = p.random.next，最后复原原链表和新链表
时间：O(n) 空间O(1)

class Solution {
    public ListNode copyRandomList(ListNode head) {
        ListNode cur = head;
        while(cur != null){
            ListNode t = new ListNode(cur.val);
            t.next = cur.next;
            cur.next = t;
            cur = t.next;
        }
        cur = head;
        while(cur != null){
            if(cur.random != null){
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        cur = head;
        while(cur != null){
            ListNode copy = cur.next;
            ListNode next = copy.next;
            cur.next = copy.next;
            p.next = copy;
            p = p.next;
            cur = next;
        }
        return dummy.next;
    }
}