Domain 2MediumCORE

Copy List with Random Pointer

We need to perform a deep copy of a singly linked list where each node has an additional random pointer. The critical constraint is that the new nodes must be distinct objects in memory, and their pointers (next, random) must reference these new nodes, not the original ones.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#Linked List

138. Copy List with Random Pointer

Model: qwen3.5:9b
Topics: Hash Table,Linked List
FAANG asked: 1
Acceptance rate: 41.4%


Problem Breakdown

We need to perform a deep copy of a singly linked list where each node has an additional random pointer. The critical constraint is that the new nodes must be distinct objects in memory, and their pointers (next, random) must reference these new nodes, not the original ones.

Inputs:

  • A head pointer to the original linked list (Node).
  • Each Node contains: val (int), next (pointer), random (pointer).

Outputs:

  • The head of a completely independent copy of this structure.

Implicit Constraints & Edge Cases:

  1. Empty List: If the input is empty (head == None), return immediately.
  2. Random Pointers to Null or Self: random can be None, point to itself, or any other node in the list (including nodes created later).
  3. Duplicate Values: Two different nodes might have the same integer value. We must distinguish them by object identity (id()), not their values.
  4. Memory Safety: The solution should ideally avoid modifying the original input structure unless necessary, though standard interview solutions often allow temporary structural changes for O(1) space optimization (which I will discuss in Intuition).

Intuition

A naive approach might be to create a new node and try to link its random pointer immediately. However, since we don’t know the memory address or index of nodes ahead of time until we traverse them, resolving an arbitrary random pointer requires knowing where that target node exists in our copy.

Why Brute Force Fails: If we simply create a new list and try to set random pointers during traversal: when processing Node A’s next, if its random points to Node B (which hasn’t been copied yet), or vice versa, we hit a dependency cycle. We need all nodes created before resolving random links efficiently without O(N^2) lookups.

Key Insight: We can use an auxiliary data structure—a Hash Map—to store the mapping between original nodes and their corresponding new cloned nodes (original -> clone).

  1. First Pass: Traverse the list, creating a copy for every node we encounter and storing it in our map. This ensures all target nodes exist before we try to link them via random.
  2. Second Pass: Iterate through the original list again (or use the stored order). For each cloned node’s random pointer, look up where its corresponding original random target is located using the same mapping logic (map[original.random]).

This guarantees O(N) time complexity and avoids complex pointer manipulation errors. While an “interleaving” technique exists to achieve O(1) extra space (by inserting copies next to originals), it modifies input structure temporarily, which can be risky if strict immutability is required or debugging becomes harder. The Hash Map approach prioritizes clarity and safety for production-like scenarios while remaining optimal in time complexity.

Approach

We will implement the Hash Map strategy:

  1. Initialize a dictionary node_map to store {original_node: new_clone} mappings.
  2. Handle the empty list case (head is None).
  3. Create a dummy head for the cloned list or initialize it directly if we track the first node created. I’ll use direct tracking of the clone’s next pointer during creation.
  4. First Pass: Traverse original. For each node:
    • Instantiate a new Node with same value.
    • Store mapping in dictionary.
  5. Second Pass: Iterate through original list again (or iterate over map keys).
    • Retrieve the cloned node from our map using current original node as key? No, we need to traverse by next pointers of original nodes to ensure order is preserved for linking randoms correctly relative to indices.
    • Actually, simpler: Iterate through the original list again (using a pointer). For each node, get its clone from map (clone = node_map[node]). If node.random exists, set clone.random = node_map[node.random].
  6. Return the head of the cloned list stored in our first iteration’s result or tracked separately.

Complexity Analysis

  • Time: O(N)O(N). We traverse the linked list twice (once to create nodes, once to link randoms). Hash map operations are O(1) on average.
  • Space: O(N)O(N) for the hash map storing references and the new node objects themselves. Note that creating N new nodes is required by definition of a deep copy; this space complexity refers strictly to auxiliary structures (the dictionary), which scales linearly with input size.

Solution

class ListNode:
    def __init__(self, x):
        self.val = int(x) if isinstance(x, str) else x # Handle string/int conversion for robustness in test envs usually not needed but safe
        self.next = None
        self.random = None

def copyRandomList(head: 'ListNode') -> 'ListNode':
    """
    Constructs a deep copy of the linked list with random pointers.
    Uses O(N) space Hash Map approach for clarity and safety against input mutation policies.
    """
    
    # Edge Case 1: Empty List
    if not head:
        return None
    
    node_map = {}
    current_original = head
    cloned_head = None
    cloned_current = None
    
    # First Pass: Create all nodes and map them to original nodes
    while current_original:
        new_node = ListNode(current_original.val)
        
        if not cloned_head:
            cloned_head = new_node
        
        node_map[current_original] = new_node
        
        # Advance pointers for next iteration of creation logic (optional optimization, 
        # but we need to track the clone head separately anyway).
        current_original = current_original.next
    
    # Second Pass: Link random pointers using the map
    current_original = head
    while current_original:
        cloned_node = node_map[current_original]
        
        if current_original.random:
            # Map lookup gives us the corresponding original target's clone directly? 
            # No, we need to find the clone of the *target* random pointer.
            # Since our map maps Original -> Clone, and we have Original.Random (which is an Original Node),
            # We can look up node_map[current_original.random] to get the cloned version of that target.
            
            if current_original.random in node_map:
                cloned_node.random = node_map[current_original.random]
        
        current_original = current_original.next
        
    return cloned_head

# Note for interview context: 
# The above logic assumes we can traverse 'head' twice without issues (which is fine).

Edge Cases Handled

  • Empty List (None): Returns None immediately.
  • Random Pointer to Null: Checked via if current_original.random. If null, clone’s random remains default/null.
  • Duplicate Values in Nodes: The dictionary keys are the Node objects themselves (identity), not their integer values. This ensures distinct nodes with same values map correctly without collision errors.
  • Random Pointer to Self or Previous/Next Node: Handled by direct object lookup (node_map[original.random]); since all original nodes exist in the map before we link randoms, any valid pointer resolves successfully.