Copy List with Random Pointer
Problem Statement
You are given the head of a linked list where each node has two pointers: next points to the next node in the ordinary chain, and random points to any node in the list or to null. Return the head of a deep copy of the list. Every copied node must be a brand-new node with the same value, and its next and random pointers must point only to copied nodes, never to original nodes.
Input
The head of a linked list. Each node is represented by its value and the index of the node its random pointer targets, or null if it has no random target.
Output
Return the head of a deep-copied linked list with identical values, identical next order, and identical random relationships among the copied nodes.
Constraints
- •
0 <= n <= 1000 - •
-10^4 <= Node.val <= 10^4 - •
Node.random is null or points to one of the nodes in the linked list
Examples
Example 1
head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
[[7,null],[13,0],[11,4],[10,2],[1,0]]Example 2
head = [[1,1],[2,1]]
[[1,1],[2,1]]Learning Objectives
- Recognise when a linked list behaves like a small graph because pointers can jump outside the next chain.
- Use a hash map to preserve the one-to-one relationship between original nodes and copied nodes.
- Wire structural pointers only after all copied nodes exist, avoiding references back into the original list.
- Understand the O(1)-extra-space interleaving trick and why it must restore the original list.
Intuition
Pattern Recognition
The signal is that each node has identity, not just value. Two different nodes may store the same value, and random can point forward, backward, to itself, or to null. That makes the list feel like a graph with two outgoing references per node, so a value-based copy is not enough. You need a stable mapping from each original node object to its copied node object.
The pointer trap is wiring too early. If you create a copy of the current node and immediately assign random by following the original pointer, the target copy may not exist yet. The clean pattern is either two passes with a map, or temporarily weaving copies between originals so every original can find its copy through original.next.
Common mistakes
- ×Copying only values and next pointers while leaving random pointers aimed at original nodes.
- ×Using node values as map keys even though values are not guaranteed to be unique.
- ×Trying to wire random pointers before every copied node has been created.
- ×In the interleaving solution, forgetting to unweave the lists and restore the original next chain.
Algorithm Explanation
Key idea
Build a one-to-one relationship from each original node to its clone. Once every clone exists, pointer wiring becomes a lookup problem: copy.next is the clone of original.next, and copy.random is the clone of original.random. A hash map makes both lookups direct and keeps object identity separate from node values.
Pointer walkthrough
Take A -> B -> C, with A.random -> C, B.random -> A, and C.random -> B. First pass creates detached nodes A', B', and C', and records A -> A', B -> B', C -> C' in the map. Second pass stands on B and reads its pointers: B.next -> C and B.random -> A. The copy B' therefore gets B'.next -> C' and B'.random -> A'. The same local rule works even for self-random pointers and null random pointers.
Algorithm
- If head is null, return null.
- Traverse the original list once and create one new node for every original node. Store original -> copy in a hash map.
- Traverse the original list again. For each original node, fetch its copy from the map.
- Assign the copy's next pointer to the mapped copy of original.next.
- Assign the copy's random pointer to the mapped copy of original.random.
- Return the copy mapped from the original head.
Solutions
Solution 1: Two-pass hash map by node identity
Use this in interviews as the primary answer. It is direct, easy to prove correct, and makes the identity mapping explicit before any pointer wiring begins.
Create all copied nodes in the first pass and remember them in a HashMap keyed by the original node object. In the second pass, wire each copy's next and random fields by looking up the copied target for the original target.
Step-by-step
- Return null immediately for an empty input list.
- Walk the original next chain and allocate a copy node for each original node.
- Store every pair as original -> copy so later pointer targets are resolved by object identity.
- Walk the original chain again and use the map to assign next and random for each copy.
- Return the copy corresponding to the original head.
O(n)
O(n)
The two passes touch each node a constant number of times, and the map stores one entry per original node.
Java implementation
Solution 2: Interleave copies for O(1) extra space
Use this when the interviewer asks for less auxiliary space and accepts temporarily modifying the list during the algorithm. Be explicit that the original list is restored before returning.
Weave each copied node immediately after its original node, so original.next temporarily becomes the copy. Then original.random.next identifies the copied random target. After random pointers are wired, separate the woven chain into the restored original list and the copied list.
Step-by-step
- For every original node, create its copy and insert it directly after the original.
- Walk the woven list and set each copy's random to original.random.next when original.random exists.
- Walk the woven list again, restoring each original node's next pointer.
- At the same time, connect copied nodes to form the copied list.
- Return the copied head from the separated clone chain.
O(n)
O(1)
The algorithm uses only a few pointers beyond the output nodes, while temporarily weaving copies into the original chain.
Java implementation
Dry Run
Sample input
Original list: A -> B -> C. Random pointers: A.random -> C, B.random -> A, C.random -> B. Trace the two-pass hash map solution.
| step | current original | map or pointer action | copied pointer result |
|---|---|---|---|
| 1 | A | Create A' and store A -> A' | A' has value A |
| 2 | B | Create B' and store B -> B' | B' has value B |
| 3 | C | Create C' and store C -> C' | C' has value C |
| 4 | A | Use A.next -> B and A.random -> C | A'.next -> B', A'.random -> C' |
| 5 | B | Use B.next -> C and B.random -> A | B'.next -> C', B'.random -> A' |
| 6 | C | Use C.next -> null and C.random -> B | C'.next -> null, C'.random -> B' |
The copied list has the same shape as the original, but every outgoing pointer lands on a copied node because each assignment goes through the original-to-copy map.
Interview Tips
Start by saying values cannot identify nodes; object identity must be preserved. Then describe the invariant map[original] = copy before writing code. If you present the interleaving follow-up, say out loud that it has three phases: weave, wire random, unweave. Interviewers care that the original list is not left mutated.
Likely follow-ups
- How would you copy the list if each node had several arbitrary extra pointers?
- How would this change if random pointers could point outside the given list?
- Can you explain the O(1)-space interleaving approach without using a hash map?
- How would you test that no copied pointer still references an original node?
Similar Problems
Key Takeaways
- Random pointers make node identity more important than node value.
- A hash map from original node to copied node turns pointer wiring into direct lookup.
- The interleaving trick uses **original.next** as a temporary route to the copy.
- A deep copy is correct only when copied pointers never reference original nodes.