← ~/lc-grind/posts

#138 - Copy List with Random Pointer

October 27, 2025

Copy List with Random Pointer

Problem Description

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]]

Example 2:


Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:


Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints:

  • 0 <= n <= 1000
  • -104 <= Node.val <= 104
  • Node.random is null or is pointing to some node in the linked list.

Solution

1. Problem Deconstruction

Technical Restatement
Given the head node of a singly linked list where each node contains:

  • val: integer data field
  • next: pointer to subsequent node
  • random: pointer to any node in the list or null

Produce a deep copy where:

  • All nodes are newly allocated with identical values
  • Topological structure is preserved (next/random relationships)
  • No pointers reference original list nodes
  • Time complexity ≤ O(n), space complexity ideally O(1) excluding output

Beginner-Friendly Explanation
Imagine you have a chain of people where each person:

  • Knows their own name
  • Points to the next person in line
  • Also randomly points to someone else in the chain

Your task: Create an identical new chain where:

  • New people have same names but are different individuals
  • Their “next” and “random” pointing matches the original exactly
  • No one in the new chain points to anyone in the old chain

Mathematical Formulation
Let L = {v₀, v₁, …, vₙ₋₁} be the original list
Define mapping f: L → L’ where:

  • f(vᵢ).val = vᵢ.val
  • f(vᵢ).next = f(vᵢ.next) ∀ i ∈ [0, n-2], f(vₙ₋₁).next = null
  • f(vᵢ).random = f(vᵢ.random) when vᵢ.random ≠ null, else null
  • f is bijective with f(vᵢ) ≠ vⱼ ∀ i,j

Constraint Analysis

  • 0 ≤ n ≤ 1000: Small enough for O(n²) but optimal exists; empty list edge case
  • -10⁴ ≤ Node.val ≤ 10⁴: Values fit in standard integers; no special handling needed
  • Node.random is null or points to list node: No cycles/dangling references; simplifies validation

2. Intuition Scaffolding

Real-World Metaphor
Creating a duplicate company org chart where:

  • Employees (nodes) have names (values)
  • Reports-to relationships (next pointers)
  • Mentor assignments (random pointers)
  • Must hire all new people but maintain identical structure

Gaming Analogy
Cloning a RPG skill tree where:

  • Nodes represent abilities
  • Arrows show prerequisite skills (next)
  • Some skills have cross-references to related abilities (random)
  • New tree must be independent but identically structured

Math Analogy
Graph isomorphism problem on a path graph with additional edges, requiring construction of isomorphic copy with node correspondence.

Common Pitfalls

  1. Shallow Copy Trap: Copying node values but reusing original pointers
  2. Random Before Creation: Setting random pointers before target nodes exist
  3. Cycle Detection Failure: Infinite loops when random pointers create cycles
  4. Null Handling: Missing checks for null random/next pointers
  5. Memory Leaks: Not freeing allocated memory in C++ implementations

3. Approach Encyclopedia

Brute Force Approach

def copyRandomList(head):
    if not head: return None
    
    # First pass: create all nodes without random pointers
    nodes = []
    curr = head
    while curr:
        nodes.append(Node(curr.val))
        curr = curr.next
    
    # Second pass: set next and random pointers
    curr = head
    for i in range(len(nodes)):
        if i < len(nodes) - 1:
            nodes[i].next = nodes[i + 1]
        if curr.random:
            # Find index of random node - O(n) search
            target = curr.random
            search = head
            idx = 0
            while search != target:
                search = search.next
                idx += 1
            nodes[i].random = nodes[idx]
        curr = curr.next
    
    return nodes[0]

Complexity: Time O(n²) from nested random pointer resolution, Space O(n) for node array

Hash Map Approach

def copyRandomList(head):
    if not head: return None
    
    mapping = {}  # original -> copy mapping
    
    # First pass: create all nodes
    curr = head
    while curr:
        mapping[curr] = Node(curr.val)
        curr = curr.next
    
    # Second pass: assign pointers using hash map
    curr = head
    while curr:
        copy = mapping[curr]
        copy.next = mapping.get(curr.next)
        copy.random = mapping.get(curr.random)
        curr = curr.next
    
    return mapping[head]

Complexity: Time O(n) two passes, Space O(n) for hash map

Interweaving Approach (Optimal)

def copyRandomList(head):
    if not head: return None
    
    # First pass: interweave original and copy nodes
    curr = head
    while curr:
        copy = Node(curr.val)
        copy.next = curr.next
        curr.next = copy
        curr = copy.next
    
    # Second pass: assign random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next
    
    # Third pass: separate lists
    curr = head
    copy_head = head.next
    while curr:
        copy = curr.next
        curr.next = copy.next
        if copy.next:
            copy.next = copy.next.next
        curr = curr.next
    
    return copy_head

Complexity: Time O(n) three passes, Space O(1) excluding output

Visualization

Original:    A → B → C → D
Random:      A → C, B → A, C → null, D → B

Step 1 (Interweave):
A → A' → B → B' → C → C' → D → D'

Step 2 (Set random):
A'.random = A.random.next = C.next = C'
B'.random = B.random.next = A.next = A'
C'.random = null
D'.random = D.random.next = B.next = B'

Step 3 (Separate):
Original: A → B → C → D
Copy:     A' → B' → C' → D'

4. Code Deep Dive

"""
# Definition for a Node.
class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution(object):
    def copyRandomList(self, head):
        if not head: 
            return None  # Edge case: empty list
        
        # FIRST PASS: Interweave original and copy nodes
        current = head
        while current:
            new_node = Node(current.val)  # Create copy with same value
            new_node.next = current.next   # Copy points to original's next
            current.next = new_node        # Original points to copy
            current = new_node.next        # Move to next original node
        
        # SECOND PASS: Assign random pointers to copies
        current = head
        while current:
            if current.random:  # Only if original has random pointer
                # Copy's random = original's random's copy
                current.next.random = current.random.next
            # else: remains None by default
            current = current.next.next  # Skip copy node
        
        # THIRD PASS: Separate intertwined lists
        current = head
        copy_head = head.next  # Save head of copy list
        while current:
            copy_node = current.next          # Current copy node
            current.next = copy_node.next     # Restore original's next
            if copy_node.next:
                copy_node.next = copy_node.next.next  # Set copy's next
            current = current.next  # Move to next original node
        
        return copy_head

Edge Case Handling

  • Example 1: Line 4 handles null head (n=0 case)
  • Example 2: Line 23 handles random=self case (node 1 points to itself)
  • Example 3: Line 19 handles null random pointers (node 0 and 2)
  • General: Line 28-32 preserves null termination correctly

5. Complexity War Room

Hardware-Aware Analysis

  • 1000 nodes × (2 pointers + 1 integer) ≈ 24KB memory
  • Fits comfortably in L1/L2 cache (32-256KB typical)
  • Three sequential passes exhibit excellent cache locality
  • Pointer chasing minimal due to spatial locality

Approach Comparison Table

Approach Time Space Readability Interview Viability
Brute Force O(n²) O(n) 8/10 ❌ Fails large N
Hash Map O(n) O(n) 9/10 ✅ Clear & correct
Interweaving O(n) O(1) 7/10 ✅ Optimal solution

6. Pro Mode Extras

Variants & Extensions

  1. Circular List: Detect cycle before copying, modify separation logic
  2. Multiple Random Pointers: Extend to node with k random pointers
  3. Persistent Data Structure: Create copy-on-write version
  4. External References: Handle random pointers to nodes outside list

Interview Cheat Sheet

  • First Mention: “This is a graph copying problem disguised as linked list”
  • Key Insight: “We need to maintain mapping between original and copy nodes”
  • Trade-off: “HashMap gives clarity, interweaving gives optimal space”
  • Verification: “Check random pointers by validating topological equivalence”
  • Testing: “Always test: empty list, single node, self-referential random”