← DSA Atlas
Dedicated problem page · #138

Copy List with Random Pointer

MediumLinked Lists and Pointer ManipulationClone with old-to-new node mappingHash map from original node to its copy
Solve on LeetCode ↗
138
MediumLinked Lists and Pointer ManipulationHash map from original node to its copyClone with old-to-new node mapping

Copy List with Random Pointer

Given a linked list where each node has a next pointer and a random pointer that can point to any node in the list or to None, build a deep copy: a brand-new set of nodes whose next and random pointers mirror the original structure. Return the head of the copied list.

Open official problem prompt ↗
In plain English

Produce an independent copy of the list whose next and random pointers replicate the original wiring but reference only new nodes.

Picture it like this

Photocopy every page of a book first, then redraw the cross-references so each copied page points to other copied pages, never the originals.

Example
Input
head = [[7,null],[13,0],[11,4],[10,2],[1,0]] (each pair is [val, random_index])
Output
[[7,null],[13,0],[11,4],[10,2],[1,0]]
Why
The copy has the same values and the same next/random wiring, but every node is a freshly allocated object.
Constraints
0 <= n <= 1000-10^4 <= Node.val <= 10^4Node.random is null or points to a node in the list
Pattern lesson

See the pattern, then code

Clone with old-to-new node mapping
Recognition clue

You must deep-copy a structure with arbitrary cross-links (random pointers), so you need a way to map each original node to its clone — a hash map or pointer interleaving.

↗
Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. If you first create every clone and remember original -> clone, then wiring each clone's next and random is just a dictionary lookup on the corresponding original pointer.

New words, made simpleKnow these before the algorithm
Deep copy
A copy whose nodes are new objects, sharing nothing mutable with the source.
Random pointer
An extra link that can target any node or None.
Node mapping
A dictionary translating each original node to its clone.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Best choiceHash map of original to clone

Clear and correct; the go-to solution.

Clone all nodes first, then wire pointers via lookups.

Time O(n)Space O(n)
Interleaved-node weaving

Saves memory but is trickier to implement correctly.

Insert each clone right after its original, set random from neighbor.random.next, then unweave.

Time O(n)Space O(1)
The rule we keep true

Invariant

After the first pass, clones contains exactly one new node per original; during the second pass every pointer assignment resolves through that complete map.

Why this is correct

Reasoning

Because all clones exist before any pointer is wired, clones.get(curr.next) and clones.get(curr.random) always find the correct copy (or None), so the copied topology is identical to the original.

The algorithm in three movesSay these aloud before coding
1First pass: create a clone for every original node and store it in a dict keyed by the original

map[7]=7', map[13]=13', ...

2Second pass: for each original, set clone.next and clone.random via dict lookups

13'.random = map[7] (index 0)

3Use dict.get so None pointers map cleanly to None

11'.random = map[1] (index 4)

4Return the clone of the original head

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
70
131
112
103
14
1 · Readwalk originals
2 · AskClone each node?
3 · Update stateclones={7:7',13:13',11:11',10:10',1:1'}
4 · Resultall copies allocated
Key takeaway

Each original node points to its freshly created clone; the second pass copies next and random through those mappings.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Empty guard

    A null head copies to null.

  2. 2
    Lines 5-9Clone every node

    First pass fills the dict so every original has a partner clone.

  3. 3
    Lines 10-14Wire next and random

    dict.get maps each original pointer to its clone, mapping None to None gracefully.

  4. 4
    Lines 15Return copied head

    The clone of the original head is the new list's head.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Empty list returns None
  • Single node whose random points to itself
  • Nodes whose random is None
  • Multiple nodes whose random targets the same node
!

Common beginner mistakes

  • Wiring pointers in the first pass before all clones exist, hitting missing keys
  • Indexing clones[curr.next] instead of using .get, crashing when next is None
  • Accidentally reusing original nodes in the copy, breaking independence
Check your understanding

Why must all clones be created before any random pointer is assigned?

More in Linked Lists and Pointer Manipulation

#206Reverse Linked ListIterative pointer reversal#141Linked List CycleFast and slow pointers (Floyd's cycle detection)#143Reorder ListFind middle, reverse second half, merge alternately#146LRU CacheHash map plus recency-ordered structure#2Add Two NumbersDigit-by-digit addition with carry#19Remove Nth Node From EndFixed-gap two pointers