Hash Map Approach

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: $O(n)$. Space: $O(n)$ for the map.