Copy List with Random Pointer
On this page
Problem statement
Each node of a linked list has a value, a
nextpointer and arandompointer that can point at any node in the list or be null. Return a deep copy: brand-new nodes with the same values, whosenextandrandompointers mirror the original structure. No pointer in the copy may point into the original list, and the original must be unchanged when you return.
The question is really about mapping: when you copy a node, how do you find the copy of the node its random points to? It is also a common warm-up for "clone a graph" questions. Original problem: LeetCode 138.
Example

Input (value, index of random): [(7, null), (13, 0), (11, 3), (10, 1)]
Output: a new list with the same pairs, made of 4 new nodes
Constraints (assumed)
- 0 ≤ n ≤ 1,000 nodes; values fit in a 32-bit integer.
What this question tests
- Building an old node → new node mapping, explicitly (hash map) or implicitly (interleaving).
- Careful pointer manipulation, including restoring the original list.
- Talking about the space trade-off between the two approaches.
Questions to ask first
- Can random point to the node itself or be null? (Yes to both.)
- May I modify the original list temporarily? (Here: yes, as long as it is restored.)
- Is O(n) extra space acceptable? If yes, the hash map version is simplest.
- Can values repeat? (Yes, so you can't map by value.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.