A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example 1:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Solution

/*
// 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> map=new HashMap<>();
        Node p=head;
        while(p!=null){
            map.put(p,new Node(p.val,p.next,p.random));
            p=p.next;
        }
        p=head;
        while(p!=null){
            Node t=map.get(p);
            t.next=map.get(p.next);
            t.random=map.get(p.random);
            
            p=p.next;
        }
        if(map.size()==0){
            return head;
        }
        return map.get(head);
        */
        if(head==null) return head;
        Node p=head;
        while(p!=null){
            Node tmp=new Node(p.val,p.next,p.random);
            p.next=tmp;
            p=tmp.next;
        }
        p=head;
        while(p!=null){
            Node tmp=p.next;
            if(p.random!=null){
                tmp.random=p.random.next;
            }
            p=tmp.next;
        }
        p=head;
    
        Node res=p.next;
        while(p!=null){
            Node tmp=p.next;
            p.next=tmp.next;
            p=p.next;
            if(tmp.next!=null){
                tmp.next=p.next;
                tmp=tmp.next;
            }
        }
        return res;
    }
}

时间O(n)
空间O(1)

不简单的题目，哈希表的方法我都没想到，用哈希表存新旧节点<Old,New>，这样就保证了新旧之间的顺序。然后在遍历一次链表改链接就行了。
不用额外空间的思路是每个节点复制到其后面的位置，第二次遍历修改链接，原来的指向节点的下一个其实就是新表该指向的位置，第三次拆解链表。