Clone a Linked List with Random Pointers

Treat random pointers as edges in a graph, not as a special case. The clearest approach makes a map from each original node to its new node in a first pass, then assigns clone.next and clone.random by looking up the original pointers in a second pass. That is O(n) time and O(n) auxiliary space. For the O(1) extra-space variant, insert each clone immediately after its original, set clone.random to original.random.next when non-null, then detach alternating nodes while restoring the original list. Explain why original.random.next is the correct clone before coding. Test null head, null random pointers, self-random pointers, and pointers that go backward. Never copy a random pointer directly into the clone because it would still point into the old list.