Problem - Copy List with Random

A linked list has nodes with an additional random pointer that can point to any node in the list or null. Create a deep copy of this list.

Example: Node 1's random points to node 3, node 2's random points to node 1. Your copy must have the same structure with new nodes.

The challenge: when copying node $A$, you might need to set its random pointer to node $B$, but $B$ might not be copied yet.

Two approaches: $O(n)$ space with a hash map, or $O(1)$ space with interleaving. Constraints: up to $1000$ nodes, values from $-10^4$ to $10^4$.