Copy List Solution

Implement the deep copy. The hash map approach is simpler to code correctly. The interleaving approach saves space but is trickier.

For interviews, start with the hash map approach. Mention the $O(1)$ space optimization if asked.

Edge cases:

• Empty list
• Single node with random pointing to itself
• Random pointers that are null

The interleaving trick appears in other problems too.

Remember it as a technique for establishing correspondence without extra space. Time: $O(n)$. Space: $O(1)$.