class Solution {
    public ListNode copyRandomList(ListNode head) {
        if (head == null) return null;
        HashMap<ListNode, ListNode> pos = new HashMap<ListNode, ListNode>();
        pos.put(null,null);
        for(ListNode p = head; p != null; p = p.next){
            pos.put(p, new ListNode(p.val));
        }
        for (ListNode p = head; p != null; p = p.next){
            pos.get(p).next = pos.get(p.next);
            pos.get(p).random = pos.get(p.random);
        }
        return pos.get(head);
    }
}