95. Copy List with Random Pointer
🔗 LeetCode Problem: 138. Copy List with Random Pointer
📊 Difficulty: Medium
🏷️ Topics: Hash Table, Linked List
Problem Statement
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.
Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
- val: an integer representing Node.val
- random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Visual:
Original:
7 → 13 → 11 → 10 → 1
↓ ↓ ↓ ↓ ↓
null 7 1 11 7
Deep copy (new nodes, same structure):
7' → 13' → 11' → 10' → 1'
↓ ↓ ↓ ↓ ↓
null 7' 1' 11' 7'
Example 2:
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Visual:
Original:
1 → 2
↓ ↓
2 2
Copy:
1' → 2'
↓ ↓
2' 2'
Example 3:
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
Constraints:
- 0 <= n <= 1000
- -10^4 <= Node.val <= 10^4
- Node.random is null or is pointing to some node in the linked list.
🌟 ELI5: The Simple Idea!
Think of photocopying a document with footnotes:
Original document:
Page 1 → Page 2 → Page 3
Page 1 has footnote pointing to Page 3
Page 2 has footnote pointing to Page 1
Page 3 has footnote pointing to Page 2
When photocopying:
❌ WRONG: Copy pages but footnotes still point to ORIGINAL pages
✓ CORRECT: Copy pages AND update footnotes to point to COPIED pages
Same with linked list:
Must copy nodes
AND update random pointers to point to copied nodes
NOT original nodes!
The Challenge:
When copying node X:
X.next = Y (easy to copy)
X.random = Z (how to find copied Z?)
Need mapping: Original → Copy
🎨 Visual Understanding
The Deep Copy Problem
Original List:
1 → 2 → 3 → null
↓ ↓ ↓
3 1 2
Goal: Create NEW list with SAME structure
Wrong approach (shallow copy):
1' → 2' → 3' → null
↓ ↓ ↓
3 1 2 ← Points to ORIGINAL nodes! ❌
Correct approach (deep copy):
1' → 2' → 3' → null
↓ ↓ ↓
3' 1' 2' ← Points to COPIED nodes! ✓
Why We Need a Map
Original:
Node A (val=7) → Node B (val=13) → Node C (val=11)
A.random = C
B.random = A
C.random = B
Creating copies:
Step 1: Create A' (val=7)
Step 2: Create B' (val=13)
Step 3: Create C' (val=11)
Step 4: Set random pointers
A'.random should point to C'
But how to find C' given C?
Solution: Map!
map[A] = A'
map[B] = B'
map[C] = C'
Now: A'.random = map[C] = C' ✓
🎯 Approach 1: HashMap (Two Pass) ⭐
The Standard Solution
Algorithm:
Pass 1: Create all new nodes, build map
- For each original node, create copy
- Store: map[original] = copy
Pass 2: Set next and random pointers
- For each original node:
copy.next = map[original.next]
copy.random = map[original.random]
Implementation
/**
* Two-pass with HashMap
* Time: O(n), Space: O(n)
*/
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// Map: original node -> copied node
Map<Node, Node> map = new HashMap<>();
// Pass 1: Create all nodes and build map
Node curr = head;
while (curr != null) {
map.put(curr, new Node(curr.val));
curr = curr.next;
}
// Pass 2: Set next and random pointers
curr = head;
while (curr != null) {
Node copy = map.get(curr);
copy.next = map.get(curr.next); // Can be null
copy.random = map.get(curr.random); // Can be null
curr = curr.next;
}
return map.get(head);
}
⏰ Time: O(n) - Two passes through the list
💾 Space: O(n) - HashMap stores n nodes
🔍 Super Detailed Dry Run
Example: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Original List:
Node A (val=7, random=null)
Node B (val=13, random=A)
Node C (val=11, random=E)
Node D (val=10, random=C)
Node E (val=1, random=A)
Structure:
A → B → C → D → E → null
↓ ↓ ↓ ↓ ↓
null A E C A
═══════════════════════════════════════════════════════════════
PASS 1: Create Nodes and Build Map
═══════════════════════════════════════════════════════════════
curr = A (val=7)
Iteration 1:
Create: A' = new Node(7)
map[A] = A'
curr = B
Map state:
A → A'
Iteration 2:
Create: B' = new Node(13)
map[B] = B'
curr = C
Map state:
A → A'
B → B'
Iteration 3:
Create: C' = new Node(11)
map[C] = C'
curr = D
Map state:
A → A'
B → B'
C → C'
Iteration 4:
Create: D' = new Node(10)
map[D] = D'
curr = E
Map state:
A → A'
B → B'
C → C'
D → D'
Iteration 5:
Create: E' = new Node(1)
map[E] = E'
curr = null
Map state:
A → A'
B → B'
C → C'
D → D'
E → E'
After Pass 1:
All copied nodes created (no connections yet)
A', B', C', D', E' are isolated nodes
Map fully built
═══════════════════════════════════════════════════════════════
PASS 2: Set Next and Random Pointers
═══════════════════════════════════════════════════════════════
curr = A
Iteration 1: Process node A
copy = map[A] = A'
Set next:
A.next = B
copy.next = map[B] = B'
A'.next = B' ✓
Set random:
A.random = null
copy.random = map[null] = null
A'.random = null ✓
curr = B
Current state of A':
A' → B' (next set)
↓
null (random set)
Iteration 2: Process node B
copy = map[B] = B'
Set next:
B.next = C
copy.next = map[C] = C'
B'.next = C' ✓
Set random:
B.random = A
copy.random = map[A] = A'
B'.random = A' ✓
curr = C
Current state:
A' → B' → C'
↓ ↓
null A'
Iteration 3: Process node C
copy = map[C] = C'
Set next:
C.next = D
copy.next = map[D] = D'
C'.next = D' ✓
Set random:
C.random = E
copy.random = map[E] = E'
C'.random = E' ✓
curr = D
Current state:
A' → B' → C' → D'
↓ ↓ ↓
null A' E'
Iteration 4: Process node D
copy = map[D] = D'
Set next:
D.next = E
copy.next = map[E] = E'
D'.next = E' ✓
Set random:
D.random = C
copy.random = map[C] = C'
D'.random = C' ✓
curr = E
Current state:
A' → B' → C' → D' → E'
↓ ↓ ↓ ↓
null A' E' C'
Iteration 5: Process node E
copy = map[E] = E'
Set next:
E.next = null
copy.next = map[null] = null
E'.next = null ✓
Set random:
E.random = A
copy.random = map[A] = A'
E'.random = A' ✓
curr = null
Final state:
A' → B' → C' → D' → E' → null
↓ ↓ ↓ ↓ ↓
null A' E' C' A'
═══════════════════════════════════════════════════════════════
Return Result
═══════════════════════════════════════════════════════════════
Return: map[head] = map[A] = A'
Deep copy complete! ✓
All pointers point to copied nodes, not originals
🎯 Approach 2: Interleaving (O(1) Space) ⭐⭐
The Space-Optimized Solution
Algorithm:
Step 1: Interleave original and copy nodes
A → B → C becomes A → A' → B → B' → C → C'
Step 2: Set random pointers
A'.random = A.random.next (the copy after original's random)
Step 3: Restore original list and extract copy
Split: A → A' → B → B' into A → B and A' → B'
Implementation
/**
* Interleaving approach (O(1) space)
* Time: O(n), Space: O(1)
*/
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// Step 1: Create copy nodes and interleave
Node curr = head;
while (curr != null) {
Node copy = new Node(curr.val);
copy.next = curr.next;
curr.next = copy;
curr = copy.next;
}
// Step 2: Set random pointers for copied nodes
curr = head;
while (curr != null) {
if (curr.random != null) {
curr.next.random = curr.random.next;
}
curr = curr.next.next;
}
// Step 3: Separate lists
Node dummy = new Node(0);
Node copyCurr = dummy;
curr = head;
while (curr != null) {
Node copy = curr.next;
// Restore original list
curr.next = copy.next;
// Build copy list
copyCurr.next = copy;
copyCurr = copy;
curr = curr.next;
}
return dummy.next;
}
⏰ Time: O(n) - Three passes
💾 Space: O(1) - No extra data structures (excluding output)
🔍 Detailed Dry Run (Interleaving)
Example: [7,null] → [13,0] → [1,0]
Original:
A(7) → B(13) → C(1) → null
↓ ↓ ↓
null A A
═══════════════════════════════════════════════════════════════
STEP 1: Interleave Copies
═══════════════════════════════════════════════════════════════
Process A:
Create A'(7)
A'.next = B
A.next = A'
A → A' → B → C → null
Process B:
Create B'(13)
B'.next = C
B.next = B'
A → A' → B → B' → C → null
Process C:
Create C'(1)
C'.next = null
C.next = C'
A → A' → B → B' → C → C' → null
After Step 1 (interleaved):
A → A' → B → B' → C → C' → null
═══════════════════════════════════════════════════════════════
STEP 2: Set Random Pointers
═══════════════════════════════════════════════════════════════
Process A:
A.random = null
Skip (no random)
Process B:
B.random = A
B'.random = A.next = A' ✓
B' → A' (random)
Process C:
C.random = A
C'.random = A.next = A' ✓
C' → A' (random)
After Step 2:
Structure:
A → A' → B → B' → C → C' → null
↓ ↓
A' A'
═══════════════════════════════════════════════════════════════
STEP 3: Separate Lists
═══════════════════════════════════════════════════════════════
Process A:
copy = A' (A.next)
Restore original:
A.next = A'.next = B
Build copy:
copyCurr.next = A'
copyCurr = A'
Process B:
copy = B'
Restore:
B.next = B'.next = C
Build copy:
A'.next = B'
copyCurr = B'
Process C:
copy = C'
Restore:
C.next = C'.next = null
Build copy:
B'.next = C'
copyCurr = C'
After Step 3:
Original: A → B → C → null
Copy: A' → B' → C' → null
↓ ↓ ↓
null A' A'
Both lists restored correctly! ✓
🎯 Approach 3: Recursive with HashMap
Recursive Solution
/**
* Recursive approach with memoization
* Time: O(n), Space: O(n)
*/
private Map<Node, Node> map = new HashMap<>();
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// If already copied, return cached copy
if (map.containsKey(head)) {
return map.get(head);
}
// Create copy
Node copy = new Node(head.val);
map.put(head, copy);
// Recursively copy next and random
copy.next = copyRandomList(head.next);
copy.random = copyRandomList(head.random);
return copy;
}
⏰ Time: O(n)
💾 Space: O(n) - HashMap + recursion stack
🎯 Comparison of Approaches
Approach Time Space Complexity Recommended
═══════════════════════════════════════════════════════════════
HashMap 2-Pass O(n) O(n) Simple ⭐⭐⭐⭐⭐
Interleaving O(n) O(1) Medium ⭐⭐⭐⭐
Recursive O(n) O(n) Medium ⭐⭐⭐
Best: HashMap (for interviews)
✓ Clearest logic
✓ Easy to explain
✓ Two clean passes
✓ Most common in interviews
Advanced: Interleaving
✓ Optimal space O(1)
✓ Shows deep understanding
✓ Great follow-up answer
✗ More complex to implement
⚠️ Common Mistakes
Mistake 1: Pointing to original nodes
// ❌ WRONG - Random points to original!
copy.random = curr.random; // Points to ORIGINAL node!
// ✓ CORRECT - Use map
copy.random = map.get(curr.random); // Points to COPY!
Mistake 2: Not handling null pointers
// ❌ WRONG - NullPointerException!
copy.next = map.get(curr.next); // What if curr.next is null?
// ✓ CORRECT - map.get(null) returns null
copy.next = map.get(curr.next); // Works! null stays null
Mistake 3: Single pass attempt (won't work)
// ❌ WRONG - Can't set random if target not created yet!
while (curr != null) {
Node copy = new Node(curr.val);
copy.random = /* ... target might not exist yet! */
}
// ✓ CORRECT - Need two passes
// Pass 1: Create all nodes
// Pass 2: Set pointers (all nodes exist now)
Mistake 4: Interleaving - wrong random assignment
// ❌ WRONG
curr.next.random = curr.random; // Points to original!
// ✓ CORRECT
curr.next.random = curr.random.next; // Points to copy!
Mistake 5: Not restoring original list (interleaving)
// ❌ WRONG - Original list modified!
// Just extract copies, don't restore original
// ✓ CORRECT - Restore original
curr.next = copy.next; // Restore original's next pointer
🎯 Pattern Recognition
Problem Type: Deep Copy with Extra Pointers
Core Pattern: HashMap Mapping (Original → Copy)
When to Apply:
✓ Deep copy linked list
✓ Clone graph/tree
✓ Multiple pointer types
✓ Need mapping between original and copy
Recognition Keywords:
- "deep copy"
- "clone"
- "random pointer"
- "additional pointer"
- "copy linked list"
Similar Problems:
- Clone Graph (LC 133) - Same pattern
- Clone N-ary Tree (LC 1490) - Tree version
- Copy List with Arbitrary Pointer - Variation
Key Components:
┌────────────────────────────────────────────┐
│ HashMap: map[original] = copy │
│ Pass 1: Create all nodes │
│ Pass 2: Set all pointers │
│ Handle Null: map.get(null) = null │
│ Time: O(n), Space: O(n) or O(1) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "I need to create a deep copy with random pointers"
Step 2: "I'll use a HashMap to map original nodes to copies"
Step 3: "Two passes: create nodes, then set pointers"
Key Points to Mention:
- Deep copy means new nodes, not shallow references
- Need mapping to find copied nodes
- Two-pass approach: create all, then connect all
- HashMap: original → copy
- map.get(null) returns null (handles null pointers)
- Alternative: O(1) space with interleaving
Walk Through Example:
"For nodes A→B→C with random pointers:
Pass 1: Create A', B', C' and build map
Pass 2: For each original node, set copy's pointers
A'.next = map[A.next] = B'
A'.random = map[A.random] = mapped copy
Result: Fully copied list with correct structure"
Follow-up Answer (if asked about O(1) space):
"I can use interleaving approach:
1. Insert copies: A→A'→B→B'→C→C'
2. Set randoms: A'.random = A.random.next
3. Split lists: separate original and copy
This uses O(1) extra space but is more complex"
Edge Cases to Mention:
✓ Empty list → return null
✓ Single node → copy with same random
✓ Random points to null → copy has null random
✓ Random points to self → copy points to self
✓ Circular random pointers → handled by map
📝 Quick Revision Notes
🎯 Core Concept:
Copy List with Random Pointer: Use HashMap to map original→copy. Pass 1: Create all copied nodes, build map. Pass 2: Set pointers using map: copy.next = map[orig.next], copy.random = map[orig.random]. Critical: map.get(null) returns null (handles null pointers). Alternative: Interleaving for O(1) space.
⚡ Quick Implementation (HashMap):
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Node {
int val;
Node next;
Node random;
Node(int val) { this.val = val; this.next = null; this.random = null; }
}
class Solution {
public static Node create(List<Integer> list) {
Node dummy = new Node(-1);
Node curr = dummy;
for(int num : list) {
curr.next = new Node(num);
curr = curr.next;
}
return dummy.next;
}
public static void print(Node head) {
Node curr = head;
while (curr != null) {
System.out.print(curr.val + " -> ");
curr = curr.next;
}
System.out.println();
}
public Node copyRandomList(Node head) {
if(head == null) {
return head;
}
// Approach 1 - using hashmap
// Create map where old node is key and new node is value.
// (A, A1) -> (B, B1) -> (C, C1) -> (D, D1) and so on simply for now.
// Why we do like this? because we do not have access to future nodes.
// Concept is every node in original list is stored in a map whose value is
// node in the newly created list. Hence in the second pass, when we access
// the random pointer, we get random pointer of the newly created list.
HashMap<Node, Node> map = new HashMap<>();
Node curr = head;
Node dummy = new Node(-1);
Node currDash = dummy;
while (curr != null) {
currDash.next = new Node(curr.val);
currDash = currDash.next;
map.put(curr, currDash);
curr = curr.next;
}
// Again pass from start now for random pointers.
// If node 2 is like (C, A), map stores (A, A'). So, (C`, map.get(A)) which is (C`, A`)
curr = head;
currDash = dummy.next;
while (curr != null) {
currDash.random = map.get(curr.random);
curr = curr.next;
currDash = currDash.next;
}
return dummy.next;
// Approach 2 - space interleaving - left as it is little complex and also not interview recommended
}
public static void main(String[] args) {
Solution t = new Solution();
Node list1 = create(Arrays.asList(1,2,3,4,5));
print(t.copyRandomList(list1));
}
}
🔑 Key Insights:
- Pattern: HashMap Mapping
- Two passes: Create all, then connect all
- Map: original → copy (enables lookup)
- Null safe: map.get(null) = null
- Deep copy: New nodes, not references
- Time: O(n), Space: O(n) or O(1) ✓
🎪 Memory Aid:
"Create all clones, then connect using map!"
"Clone → Map → Connect!" ✨
⚠️ Critical Rule:
NEVER point to original nodes!
❌ WRONG:
copy.random = orig.random // Points to original!
✓ CORRECT:
copy.random = map[orig.random] // Points to copy!
The map is the KEY to finding copied nodes!
🧪 Edge Cases
Case 1: Empty list
Input: head = null
Output: null
Handled: Early return
Case 2: Single node, random to self
Input: [[1,0]]
Node points to itself
Output: [[1,0]]
Copy also points to itself
Case 3: All random pointers null
Input: [[1,null],[2,null],[3,null]]
Output: [[1,null],[2,null],[3,null]]
Handled: map.get(null) = null
Case 4: Random forms cycle
A.random = B, B.random = A
Handled: Map prevents issues
All handled perfectly! ✓
Related Problems
- Clone Graph (LC 133) - Same HashMap pattern
- Clone Binary Tree with Random Pointer (LC 1485) - Tree version
- Clone N-ary Tree (LC 1490) - N-ary tree
Happy practicing! 🎯
Note: This problem teaches the fundamental deep copy pattern using HashMap! This exact pattern appears in graph cloning, tree cloning, and many other problems. The two-pass approach (create all, then connect all) is the key insight. Master this and you'll handle any cloning problem! 💪✨