• The number of nodes is in the range [0, 1000]
• -10⁴ <= Node.val <= 10⁴
• random points to a node in the list, or is null

A deep copy means new nodes all the way down: not just copied values, but copied links — every next and every random in the clone must point to a clone, never back into the original. The plain next pointers are easy (walk and copy in order). The random pointers are the whole difficulty.

Copying next is easy because it goes forward: when you're building clone of node A and need A.next's clone, you can just create it now. But A.random can point anywhere — often to a node further down the list that you haven't reached yet, so its clone doesn't exist to point at. You cannot set cloneA.random until clone(A.random) has been created, and you can't guarantee that ordering while walking once. The core need is a way to answer, for any original node, "what is your clone?" — regardless of where it sits.

Give each original node an entry in a hash map: original → its clone. Do two passes. First pass: walk the list and create a bare clone (value only) for every node, recording the pairing in the map. Now every clone exists. Second pass: walk again and wire the clones using the map — clone.next = map[original.next], clone.random = map[original.random]. Because the map already holds a clone for every original (and we map null to null), the random target always exists, no matter how far it jumps. Clear and correct, at the price of O(N) extra space for the map.

if not head: return None
clones = {None: None}          # map None -> None so null links copy cleanly

curr = head                    # pass 1: make every clone, record the pairing
while curr:
    clones[curr] = Node(curr.val)
    curr = curr.next

curr = head                    # pass 2: wire next and random via the map
while curr:
    clones[curr].next = clones[curr.next]
    clones[curr].random = clones[curr.random]
    curr = curr.next
return clones[head]

The map only exists to answer "where is X's clone?" We can make that answer free by putting each clone immediately after its original in the list itself, so a node's clone is always node.next. Three passes:
- Interleave: after each original node X, splice in its clone X', giving X → X' → Y → Y' → … Now clone(X) is literally X.next.
- Wire randoms: for each original X, its clone is X.next and the clone of X.random is X.random.next. So X.next.random = X.random.next — the map lookup becomes a one-hop pointer step.
- Detach: unweave the two lists, restoring every original's next and stitching the clones together into their own list.

if not head: return None

curr = head                    # 1. interleave clones into the original
while curr:
    clone = Node(curr.val)
    clone.next = curr.next
    curr.next = clone
    curr = clone.next

curr = head                    # 2. wire clone randoms from neighbors
while curr:
    if curr.random:
        curr.next.random = curr.random.next
    curr = curr.next.next

curr = head                    # 3. split original and clone back apart
clone_head = head.next
while curr:
    clone = curr.next
    curr.next = clone.next            # restore original link
    clone.next = clone.next.next if clone.next else None
    curr = curr.next
return clone_head

Both solutions are O(N) time; the map version costs O(N) space, the interleave version O(1) extra (ignoring the output the problem requires). The transferable idea is the interleave trick: when you need a lookup from old thing to new thing, you can sometimes store the new thing physically adjacent to the old one and replace the map with a pointer hop. It's a niche move, but it captures the general reflex — an O(N)-space association can occasionally be encoded into the structure you already have, if you can weave the copy in and cleanly unweave it afterward.