Linked Lists
Mapping old nodes to new ones
When you must copy a structure whose links point anywhere, build the nodes first and the links second.
Key idea
The difficulty with copying
Copying a plain list is easy because you only ever need the node you are about to create next. Copying a structure where nodes point at arbitrary other nodes is harder: when you reach node A and it points at node Z, the copy of Z may not exist yet.
Trying to handle that inline leads to recursive creation and bookkeeping about what has already been made. There is a much simpler answer.
Why it works
Nodes first, links second
Pass one: walk the original and create a copy of every node, storing a map from each original node to its copy. Set no links at all.
Pass two: walk the original again. For each original node, look up its copy, and set that copy's links by looking up the copies of whatever the original pointed at.
By the second pass every copy exists, so no lookup can fail and no ordering question arises. The awkwardness disappears entirely.
Below is pass one only, ending with the check that makes pass two trivial: every node any link could possibly point at is already a key in the map.
Tip
`copies.get` handles `None` for free
dict.get returns None for a missing key, and None is exactly what a copy's link should be when the original's link was None. So no branch is needed.
Using copies[node.next] instead would raise KeyError on the last node. This is a small thing that removes a special case, in a unit where special cases are most of the difficulty.
Gotcha
The map is keyed by node identity
The keys are node objects, not values. Two nodes holding the same value are different keys, which is what you want, since they are different nodes and need different copies.
This works because a plain object is hashable by identity. If the node class defined __eq__ without __hash__, it would stop being hashable and this approach would break, which is worth knowing if you ever write the class yourself.
Tip
Checking that it is really a copy
The last printed line is the check that matters. A copy that shares nodes with the original is not a copy, and it is easy to produce one by accident by assigning original references into the new structure.
Whenever you write a deep copy, assert somewhere that the new nodes are not the old ones. It is a one-line test that catches an entire class of subtly wrong answers.
Cost
Cost, and the O(1) alternative
Two passes and a map give O(n) time and O(n) space. There is a well-known O(1) space version that interleaves each copy directly after its original, uses that adjacency to resolve the arbitrary links, then unweaves the two lists.
It is genuinely clever and considerably easier to get wrong. Offer the map version, state its cost, and mention the interleaving trick as the follow-up. Being able to describe it is usually worth as much as implementing it.
Predict the output: setting links during the first pass
This tries to do it in one pass, creating each copy and wiring its jump link immediately. Type the two values it prints, separated by a single space.
Copy List With Random Pointer
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.