Two passes: first create all clones, then wire their next and random pointers using the map.
function copyRandomList(head):
if head is null:
return null
map = {}
current = head
while current:
map[current] = Node(current.val)
current = current.next
current = head
while current:
map[current].next = map.get(current.next, null)
map[current].random = map.get(current.random, null)
current = current.next
return map[head]
time, space.