Use a hash map to track original → copy correspondence:
map = {}
# First pass: create all copy nodes
current = head
while current:
map[current] = new Node(current.val)
current = current.next
# Second pass: set next and random pointers
current = head
while current:
if current.next:
map[current].next = map[current.next]
if current.random:
map[current].random = map[current.random]
current = current.next
return map[head]
First pass creates all copies. Second pass connects them using the map to find the corresponding copy nodes.
Time: . Space: for the map.