On this page
Description
Some linked lists give each node an extra random pointer to any node in the list. Deep-copying one means every pointer in the copy must point at another copy, never back into the original. The standard answer keeps a map from each original node to its clone. Create all the clones first, then wire next and random through the map. A space-saving alternative weaves each clone in right after its original, then separates the two lists.
We'll go from simple to more technical:
- The pattern: original-to-clone map, two passes.
- A second flavor: interleave the clones, wire them, then un-interleave.
- Where this is the general recipe for copying object graphs.
- The wiring bugs, and when the extra map memory matters.
The approach
Copying a plain list is one walk. The random pointer is what makes this hard. To wire a clone's random, the clone of its target must already exist, and the target can be anywhere, even further down the list. So do it in two passes. First create every clone, unwired, and remember each one in a map from original to clone. Then walk again and wire each clone's next and random by looking their targets up in the map.
Take 7 -> 3 -> 5, where 7's random points ahead to 5 and 3's points back to 7:
| Pass | At node | What happens |
|---|---|---|
| 1 | each node | clones 7', 3' and 5' are made; the map is {7: 7', 3: 3', 5: 5'} |
| 2 | 7 | 7'.next = map[3] = 3', and 7'.random = map[5] = 5' |
| 2 | 3 | 3'.next = 5', and 3'.random = map[7] = 7' |
| 2 | 5 | 5'.next = map[null] = null, and 5'.random = null |
Wiring 7' in the first pass would have failed: 5' didn't exist yet.
Java
Map<Node, Node> map = new HashMap<>();
Node cur = head;
while (cur != null) { // pass 1: create every clone, unwired
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
while (cur != null) { // pass 2: wire the clones using the map
map.get(cur).next = map.get(cur.next); // map.get(null) is null - handles the tail cleanly
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
Python
def copy_random_list(head: Node | None) -> Node | None:
clone = {}
cur = head
while cur is not None: # pass 1: create every clone, unwired
clone[cur] = Node(cur.val)
cur = cur.next
cur = head
while cur is not None: # pass 2: wire the clones using the dict
clone[cur].next = clone.get(cur.next) # .get(None) is None - handles the tail cleanly
clone[cur].random = clone.get(cur.random)
cur = cur.next
return clone.get(head)
Looking up null returns null, so the tail and missing random pointers need no special case.
A second flavor: interleaving clones into the original list
The map costs O(n) extra memory. You can avoid it by placing each clone right after its original: 7 -> 7' -> 3 -> 3' -> 5 -> 5'. Then any node's clone is simply its next, and that layout does the map's job:
Pass 1: after every original node, insert its clone: 7 -> 7' -> 3 -> 3' -> 5 -> 5'
Pass 2: for every original X with a random pointer, set X'.random = X.random.next
(the clone of X.random sits right after it)
Pass 3: walk the chain again and unthread it: the originals link up as before,
and the clones form their own list
For 7, 7.random is 5, and 5.next is 5', exactly the clone 7' should point to. The price is the third pass. It must restore the original list's next pointers as well as pull out the clones, and a slip there damages the input, which the map version never touches.
Where you'll see it
This is the general recipe for deep-copying any object graph with cross-references, cycles or shared objects. Keep a map from original to copy, and fill it in before following references. Python's copy.deepcopy does exactly that with its memo dictionary: it records each copy before copying its fields.
Which tool for which job?
| You need | Use |
|---|---|
| Copy a list with random pointers, simply | an original→clone map, two passes |
| The same with O(1) extra space | interleave clones, wire random, un-interleave |
| Copy any object graph (cycles, shared nodes) | the same map, filled before following references |
| Nodes that override equals/hashCode (Java) | IdentityHashMap |
Python nodes that define __eq__ | key the map by id(node) |
| A quick copy in Python | copy.deepcopy - for short structures only |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
Wiring random while still creating clones | forward targets aren't cloned yet | create every clone first |
Pointing a clone's random at an original | the copy shares nodes with the input | always look the target up in the map |
| A value-equality map key | equal nodes share one clone | an identity map |
| Skipping the un-interleave pass | the input stays threaded with clones | separate both lists |
copy.deepcopy on a long list | RecursionError | the iterative map version |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why can't a clone's random be wired in the same pass that creates the clones?
Show answer
random can point to a node further down the list, which hasn't been cloned yet. In the example, 7 points to 5. A single forward pass would look up a clone that doesn't exist yet.
2. map.get(cur.next) runs even at the tail, where cur.next is null. Why no null check?
Show answer
Null was never put in the map, so looking it up returns null. That's exactly what the tail's clone should have as its next. The map already does the right thing.
3. In the interleaved version, why is cur.random.next the clone of cur.random?
Show answer
Pass 1 put every original's clone right after it. cur.random is an original node, so its clone sits at its next. The layout itself does the map's job.
Key takeaways
- Create every clone first, then wire them. A
randomtarget's clone must exist before you wire to it. - Looking up null in the map returns null, which handles the tail and missing pointers.
- Interleaving each clone after its original makes "find the clone" just
.next, with no map, but needs a careful third pass to separate the lists. - Both are O(n) time. The trade is O(n) extra space and simple code, against O(1) space and trickier pointer work.