LeetCode · #138

Copy List with Random Pointer Solution

Construct a deep copy of a linked list where each node has an additional random pointer to any node or null.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #138

🏗️

Pattern

Deep Copy — HashMap or interleave

A linked list of length n is given where each node has an additional random pointer that could point to any node in the list, or null. Construct a deep copy of the list — new nodes with the same value, next, and random structure.

Constraints

 • 0 ≤ n ≤ 1000 • -10⁴ ≤ Node.val ≤ 10⁴ • random points to a node in the list or null 

Section Two · Approach 1

HashMap — O(n) space

Two passes: (1) Create a copy of each node and store old→new mapping in a HashMap. (2) Walk through and assign next and random pointers using the map. The map lets us look up the new copy of any original node in O(1).

Why it works

The random pointer can point to any node — we can't set it until all copies exist. The HashMap bridges old and new: for any original node, map.get(original) gives its copy.

🎯 This is the clearest approach and works in interviews. The interleave approach below saves space but is harder to explain and implement correctly.

Section Three · Approach 2

Interleave & Separate — O(1) extra space

Three passes without a hashmap: (1) Insert a copy of each node right after the original: A→A'→B→B'→... (2) Set random pointers: copy.random = original.random.next. (3) Separate the interleaved list into original and copy.

💡 Mental model: Imagine each person in a line clones themselves and the clone stands right behind them. Now to find a clone's "random friend," just look at the original's random friend's clone (the one right behind them). Finally, every other person steps out to form the copy line.

Algorithm

Pass 1 — Interleave: For each node A, create A' and insert: A→A'→B→B'→...
Pass 2 — Random pointers: A'.random = A.random.next (A.random points to original, .next is its copy).
Pass 3 — Separate: Extract copies: A.next = A'.next, A'.next = (A'.next != null ? A'.next.next : null).

Section Four · Trace

Visual Walkthrough

HashMap approach for list: A(random→C) → B(random→A) → C(random→null):

HashMap — two-pass deep copy

Section Five · Implementation

Code — Java & Python

Java — HashMap approach

 import java.util.HashMap;
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
HashMap<Node, Node> map = new HashMap<>();
// Pass 1: Create copies Node curr = head;
while (curr != null) {
            map.put(curr, new Node(curr.val));
            curr = curr.next;
        }
// Pass 2: Wire next and random
curr = head;
while (curr != null) {
            map.get(curr).next = map.get(curr.next);
            map.get(curr).random = map.get(curr.random);
            curr = curr.next;
        }
return map.get(head);
    }
}

Python — HashMap approach

 class Solution:
def copyRandomList(self, head):
if not head: return None
old_to_new = {}
# Pass 1: Create copies
curr = head
while curr:
            old_to_new[curr] = Node(curr.val)
            curr = curr.next
# Pass 2: Wire next and random
curr = head
while curr:
            old_to_new[curr].next = old_to_new.get(curr.next)
            old_to_new[curr].random = old_to_new.get(curr.random)
            curr = curr.next
return old_to_new[head]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
HashMap	O(n)	O(n)	Clean, easy to understand. Map stores old→new.
Interleave ← space-optimal	O(n)	O(1)	Three passes, no extra map. Trickier pointer work.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty list	`null`	Return null immediately.
Single node, random=self	`A→null, A.random=A`	Copy's random must point to the copy, not the original.
All random=null	Standard list	Degenerates to normal copy — random stays null.

⚠ Common Mistake: Setting copy.random = original.random directly (without mapping). This makes the copy's random point to a node in the original list, not the copy — the deep copy is broken.

← Back to Linked List problems

LearningTree

LC 138 · Copy List with Random Pointer — Solution & Explanation | DSA Guide