Pattern this teaches:Linked List Manipulation
Copy List with Random Pointer
A medium Linked List interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Linked List
- Sheets
- 2
- Core for
- 4 roles
The problem
Each node in this linked list has two links: the usual next, plus a random link that may point at any node of the list or at nothing. Build a completely separate copy of the list, with fresh nodes whose next and random links mirror the original's, and return the copy's first node.
Example 1
- Input
- [[5,2],[7,null],[9,0],[6,3],[2,1]]
- Output
- deep copy with same structure
Example 2
- Input
- [[10,1],[20,0]]
- Output
- deep copy with same structure
Example 3
- Input
- [[3,null]]
- Output
- deep copy of single node
Constraints
- 0 <= n <= 1000
- -10^6 <= Node.val <= 10^6
How to think about it
Updated 2026-09-29Copying nodes sequentially is simple, but random pointers can target nodes that have not been cloned yet. You must either keep a dictionary mapping original nodes to clones, or interweave clones directly beside originals so each clone finds its random target by looking at the original's next step.
Approaches, worst first
Hash map dictionary
time O(n) · space O(n)
Traverse the list once to instantiate a clone for every original node, storing mappings in a hash map `original -> clone`. Perform a second pass assigning `clone.next` and `clone.random` by looking up corresponding pointers in the map.
Interweaving nodes in placeWrite this one
time O(n) · space O(1)
Insert each cloned node directly after its original counterpart: `A -> A' -> B -> B'`. In a second pass, set `curr.next.random = curr.random.next`. In a third pass, decouple the interwoven chain into the original list and the clone list, achieving O(1) auxiliary space.
Where people lose marks · 3
- Dereferencing `curr.random.next` when `curr.random` is null triggers an unhandled null pointer exception.
- Failing to restore the original list's next pointers during decoupling mutates the input list, which breaks caller expectations.
- Handling an empty input list with `head == null` without an immediate guard causes initial property lookups to crash.
The theory behind it
Linked List — the ground this problem stands on. All Linked List problems
What Linked List is
A linked list is a chain of separate cargo cars connected by coupling hooks, scattered anywhere across memory rather than sitting in a tidy contiguous row. Each car, called a node, holds a single piece of data and a pointer directing traffic to the address of the next car in line. Because nodes connect only by directional links, jumping straight to the tenth car is impossible without walking past the first nine.
When to reach for it
Choose a linked list when a problem requires frequent insertions and deletions at known positions without shifting whole blocks of surrounding memory. Problems mentioning pointer splicing, reversing subsequences in place, merging sorted streams, or detecting cycles in linear chains strongly point here. It is ideal when total capacity is unpredictable and memory allocation must happen one individual node at a time.
How the pattern works
Think in terms of pointer rewiring before dereferencing. Keep a dummy head node pointing to the start of the list so modifications to the initial item do not require separate edge logic. Always save references to neighboring nodes into temporary variables before cutting or redirecting forward links. When diagnosing loops or locating middle nodes, advance two references simultaneously at differing velocities so traversal completes without supplementary storage.
More Linked List problems
Target Roles
Core requirement for 4 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .