Introduction to Clone Pattern

You are given a linked list where each node has the usual next pointer and one extra pointer to any node in the list. Produce an independent copy.

A -> B -> C
A.random = C     B.random = A     C.random = B

Walking the list and copying the values builds the next chain correctly. The extra pointers are the problem.

When node A is copied, its extra pointer refers to C, and the copy of C does not exist yet. Pointing at the original C would be wrong, because the copy would then share nodes with the original.

The fix is to keep a record