Problem Statement

Given a linked list where each node has two pointers: 'next' pointing to the next node and 'random' pointing to any node in the list or null, return a deep copy of the entire list such that the copied nodes have the same values and the same 'next' and 'random' pointer structure as the original list.

LeetCode: 138. Copy List with Random Pointer

How the Algorithm Works

💡 One Sentence Rule (Key Insight)

Use a hashmap to map each original node to its copy, enabling constant-time lookup for correct pointer assignment during the two-pass deep copy process.

This rule captures the ESSENCE of the algorithm. The random pointers can point anywhere, making a single-pass copy impossible. The hashmap transforms a potentially quadratic problem into linear time.

Algorithm Overview

The algorithm performs a two-pass approach with a hashmap to handle the arbitrary random pointer connections:

Pass 1: Node Creation

  • Iterate through the original list
  • Create a copy of each node (value only, no pointers set)
  • Store mapping: original_node → copied_node in hashmap
  • Also map None → None to handle null pointers

Pass 2: Pointer Assignment

  • Iterate through the original list again
  • For each copied node, set its next and random pointers
  • Use hashmap to lookup the copies: copy.next = hashmap[original.next]
  • Return the copy of the original head

Step-by-Step Process

  1. Initialize hashmap → Include None → None mapping for null pointers
  2. First pass: Create all node copies → Iterate original list, create copies, store in hashmap
  3. Second pass: Assign pointers → Use hashmap to set next and random pointers correctly
  4. Return deep copy → Return hashmap[head] as new list head

The key insight is that we cannot assign pointers during the first pass because the target nodes might not be created yet. By separating node creation from pointer assignment, we guarantee all nodes exist before we try to reference them.

Input

head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Represents:

Node 0: val=7,  next=Node 1, random=null
Node 1: val=13, next=Node 2, random=Node 0  
Node 2: val=11, next=Node 3, random=Node 4
Node 3: val=10, next=Node 4, random=Node 2
Node 4: val=1,  next=null,   random=Node 0

Output

[[7,null],[13,0],[11,4],[10,2],[1,0]]

A completely independent deep copy with the same structure and pointer relationships.

Solution Code

   def copy_random_list(head: 'Node') -> 'Node':
        if not head:
            return None

        old_to_copy = { None: None }

        curr = head
        while curr:
            copy = Node(curr.val)
            old_to_copy[curr] = copy
            curr = curr.next
        
        curr = head
        while curr:
            copy = old_to_copy[curr]
            copy.next = old_to_copy[curr.next]
            copy.random = old_to_copy[curr.random]
            curr = curr.next
        
        return old_to_copy[head]

The Hashmap Solution Explained

  1. Problem with naive approach: If we tried to copy nodes and assign pointers in one pass, we'd encounter nodes we haven't created yet when following random pointers.

  2. Two-pass advantage: By creating all nodes first, we guarantee that every node exists before we try to reference it during pointer assignment.

  3. Constant-time lookups: The hashmap provides O(1) access to any node's copy, avoiding the need to search through the list.

  4. Handles all edge cases: The None → None mapping elegantly handles null pointers without special case code.

Complexity Analysis

Time Complexity: O(n)

  • First pass: O(n) to create all node copies
  • Second pass: O(n) to assign all pointers
  • Hashmap operations (insert/lookup): O(1) average case
  • Total: O(n)

Space Complexity: O(n)

  • Hashmap stores one entry per node: O(n)
  • New linked list nodes: O(n)
  • Total: O(n) auxiliary space

The space complexity is optimal since we must create n new nodes for the deep copy.

Alternative Approaches

1. Interweaving Approach (O(1) extra space)

Create copies by inserting them between original nodes, then extract the copied list. More complex but uses no extra hashmap space.

2. Recursive with Memoization

Use recursion with a hashmap for memoization. Similar time/space complexity but different code structure.

Key Takeaways

  1. Deep copy with complex pointers requires careful ordering - separate node creation from pointer assignment
  2. Hashmap enables constant-time node lookup - transforms quadratic search into linear algorithm
  3. Handle null pointers gracefully - include None → None in hashmap to avoid special cases
  4. Two-pass approach is often cleaner - don't try to do everything in one pass if it complicates the logic

Common Pitfalls

❌ Trying to assign pointers during node creation - target nodes may not exist yet ❌ Forgetting to map None to None - causes errors when accessing null pointers
❌ Not handling empty input - check for head = None case ❌ Modifying original list - ensure deep copy is completely independent

Practice Problems