Skip to content

Volume ITechnology

4.9.5 — Copy List with Random Pointer ​

LeetCode 138 · Medium · ★ Blind 75

The problem ​

You are given the head of a linked list where every node has two pointers. next points to the following node, as usual. random can point to any node in the list, including the node itself or an earlier one, or it can be null. Make a deep copy of the list and return its head.

A deep copy is a completely new set of nodes with the same values and the same pointer shape. No pointer in the copy may point back into the original list.

original:  7 → 13 → 11 → 10 → 1
random:    7→null, 13→7, 11→1, 10→11, 1→7

the copy must have new nodes 7', 13', 11', 10', 1'
with 13'.random = 7', 11'.random = 1', and so on

The list has between 0 and 1,000 nodes.

What the problem is really asking ​

Copying next alone is easy. Walk forward and build a new node for each old one.

random is the problem. Suppose you are copying node 13, and its random points to node 7. You need 13'.random to point to 7', the copy of 7, not to the original 7. And for some nodes, the target's copy may not exist yet. When you copy node 11, its random points to node 1, which you have not reached.

So the real question is: how do you find "the copy of this old node", even for nodes you have not copied yet?

The brute force, and where it wastes work ​

Copy the list using only next. Then, for each original node, count how many steps from the head its random target sits. Walk the same number of steps in the copy, and point the copy's random there.

Counting the steps for one node takes up to n steps. Doing it for all n nodes is O(n^2).

The waste in one sentence: it rediscovers each node's position by walking from the head, again and again, when a lookup table could remember "old node → its copy" once.

The idea ​

Do it in two passes, with a hash map from each old node to its new copy.

  1. First pass. Walk the original list and create a copy of every node, with the right value but no pointers yet. Record each pair in the map: old node → new node.
  2. Second pass. Now every copy exists. Walk the original list again. For each old node, look up its copy, and set the copy's next and random by looking up the copies of the old node's next and random.

Think of cloning a group of friends who are holding hands in a line and each pointing at their best friend. In the first pass, you make a clone of every person and stand them in a corner, writing in a notebook "original Bob → clone Bob". In the second pass, you look at original Bob. He holds hands with original Alice and points at original Charlie. You look in the notebook to find clone Alice and clone Charlie, and tell clone Bob to hold hands with one and point at the other.

The solution ​

python
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:                                     # (1)
            return None

        old_to_new = {}                                  # (2)

        curr = head                                      # (3)
        while curr:
            old_to_new[curr] = Node(curr.val)
            curr = curr.next

        curr = head                                      # (4)
        while curr:
            copy = old_to_new[curr]                      # (5)
            copy.next = old_to_new.get(curr.next)        # (6)
            copy.random = old_to_new.get(curr.random)    # (7)
            curr = curr.next

        return old_to_new[head]                          # (8)
ts
function copyRandomList(head: Node | null): Node | null {
  if (!head) return null;                                // (1)

  const oldToNew = new Map<Node, Node>();                // (2)

  let curr: Node | null = head;                          // (3)
  while (curr) {
    oldToNew.set(curr, new Node(curr.val));
    curr = curr.next;
  }

  curr = head;                                           // (4)
  while (curr) {
    const copy = oldToNew.get(curr)!;                    // (5)
    copy.next = curr.next ? oldToNew.get(curr.next)! : null;        // (6)
    copy.random = curr.random ? oldToNew.get(curr.random)! : null;  // (7)
    curr = curr.next;
  }

  return oldToNew.get(head)!;                            // (8)
}

Line by line ​

(1) An empty list copies to an empty list.

(2) The notebook. A map whose keys are the original node objects and whose values are their copies.

Using node objects as keys works because, by default, Python and JavaScript compare objects by identity, meaning "is this the very same object in memory". Two different nodes that happen to hold the same value stay separate keys. That is exactly what we want here, because each original node needs its own copy.

This is the opposite of 4.4.4 Group Anagrams. There, comparing arrays by identity was the bug, because we wanted arrays with equal contents to match. Here we are tracking particular objects, so identity is right.

(3) First pass: create every copy. For each original node, make a new node with the same value and record the pair. No pointers are set yet, because the targets may not exist yet.

(4) Second pass. Walk the original list again. Now every copy exists.

(5) Find this node's copy.

(6) Set the copy's next to the copy of the original's next. We use .get(...) instead of [...]. When curr.next is None, None is not a key in the map, so old_to_new[None] would raise an error. .get(None) returns None instead, which is exactly the value we want to store. One method call replaces an if.

(7) Set the copy's random the same way.

(8) Return the copy of the head.

Trace ​

Take a three-node list: A → B → C, where A.random = C, B.random = A, and C.random = None.

After the first pass, the map holds A → A', B → B', C → C'. The copies have values but no pointers.

Second pass:

currcopycopy.next = copy of curr.nextcopy.random = copy of curr.random
AA'B'C'
BB'C'A'
CC'NoneNone

The copy is A' → B' → C', with A'.random = C' and B'.random = A'. Not one pointer leads back into the original.

Complexity, derived ​

Time. Each pass walks the list once, doing constant-time map work per node. Two passes of n steps is 2n, which is O(n).

Space. The map holds one entry per node, so it uses O(n) extra memory. (The copied list itself is the answer, so it is not counted as extra.)

The version with no map ​

There is a clever solution that stores the "old → copy" link inside the list itself, so no map is needed.

Step 1. Put each copy right behind its original.

A → B → C
becomes
A → A' → B → B' → C → C'

Now, for any original node curr, its copy is simply curr.next.

Step 2. Set the random pointers. The copy of curr.random is curr.random.next. So:

python
curr.next.random = curr.random.next if curr.random else None

The list's own shape is doing the job the map was doing.

Step 3. Separate the two lists, and restore the original's next pointers.

python
class Solution:
    def copyRandomList(self, head):
        if not head:
            return None

        curr = head                                     # 1. weave copies in
        while curr:
            curr.next = Node(curr.val, curr.next)       # new node points to the old next
            curr = curr.next.next                       # jump over the new node

        curr = head                                     # 2. set randoms
        while curr:
            if curr.random:
                curr.next.random = curr.random.next     # the copy of the target
            curr = curr.next.next

        old, new_head = head, head.next                 # 3. unweave
        while old:
            copy = old.next
            old.next = copy.next                        # original skips its copy
            copy.next = copy.next.next if copy.next else None   # copy skips the next original
            old = old.next

        return new_head

This is O(n) time and O(1) extra memory. It takes three passes instead of two, and it changes the input list for a while, which is a real objection in shared code.

Lead with the map version. It is clearly correct and easy to explain. Offer the woven version when asked to save memory, and mention that it temporarily changes the input.

Edge cases ​

  • Empty list. Line (1) returns None.
  • A node whose random points to itself. The map lookup returns its own copy. Correct.
  • Every random is None. .get(None) returns None each time.
  • Nodes with equal values. Identity keys keep them separate.

Variations you will meet ​

  • Clone Graph. The same problem on a graph instead of a list. The walk becomes a depth-first or breadth-first search, and the map does exactly the same job. See 4.20.2. If you see these two as one problem, you understand both.
  • Deep-copying any data with shared references. When a program copies an object that refers to the same inner object twice, it keeps a map of "already copied" objects, so that inner object is copied once and both references point to the same copy. That is this page, in real software.

The general lesson: when a copy must keep references to objects that may not exist yet, create all the objects first while recording old → new, then wire the pointers in a second pass.

What the interviewer will push on ​

"Why can't you do it in one pass?" A random pointer can point forward to a node whose copy does not exist yet. Saying this before you code shows you understood the problem.

"What are the keys in your map?" The original nodes themselves, compared by identity. Using values as keys would merge different nodes that share a value.

"Can you do it without the map?" The weaving trick. Mention its cost: it changes the input for a while.

"How does this relate to cloning a graph?" Same problem, different walk.

One thing to volunteer: say that real deep-copy routines do exactly this with shared references. It shows you know the problem is real.

Next: 4.9.6 Add Two Numbers. Arithmetic on a list, with a carry that must survive past the end.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet