Clone list with random pointers

Question

You are given the head of a singly linked list where each node has two pointers: next and random. The random pointer may be null or point to any node in the list (including itself). Construct a deep copy of the list and return the head of the copy. The copied list must consist of brand-new nodes, and each copied node's next/random must point to the corresponding copied node, never to a node in the original list.

1. Core deep copy. Build a deep copy in O(n) time. Walk through the original once and reproduce both the next chain and the arbitrary random links among the new nodes.
2. Hash-map approach. Explain the straightforward solution that uses a map from each original node to its clone, then a second pass to wire up next and random. State its O(n) time and O(n) auxiliary space.
3. In-place weaving approach. Explain the interleaving (weave/unweave) technique that achieves O(1) auxiliary space beyond the new nodes: clone each node and splice it directly after its original (A -> A' -> B -> B' -> ...), assign each clone's random from orig.random.next, then unweave the two lists to restore the original and extract the copy.
4. Handling cycles in random pointers. Discuss why the algorithm stays correct when random pointers form cycles or point backward (you copy links, not by traversal order, so cycles never cause infinite loops or re-cloning).
5. Verifying correctness. Describe how you verify structural equality of the copy against the original: same length, equal node values in order, the random of each copied node maps to the correct relative position, and that no copied pointer escapes into the original list (deep-copy isolation).
6. Corner cases. Make sure the solution handles an empty list, a single-node list (including a node whose random points to itself), and a list where every random is null.