Copy List with Random Pointer Algorithm Solution

The Copy List with Random Pointer problem requires creating a deep copy of a linked list where each node has a random pointer that can point to any node in the list or null. This classic DSA problem tests understanding of linked list manipulation and memory management techniques.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we modify the input list during copying, or must we preserve the original structure?
2. What is the maximum size of the input list (e.g., can we assume it's under 10^6 nodes)?
3. Are there any constraints on the random pointers (e.g., can they point to null or only nodes in the list)?
4. Should we return a deep copy of the list with all pointers properly redirected?
5. Do we need to handle cycles in the random pointer structure?

Restatement of problem: Given a linked list where each node has a next pointer and a random pointer that can point to any node in the list (including itself) or null, create a deep copy of this list such that all new nodes have their next and random pointers pointing to the corresponding new nodes in the copied list.

Input/Output specification:

• Input: A head node of a linked list with val, next, and random fields
• Output: Head of a new linked list with identical structure but completely separate nodes

Constraints and assumptions:

• Each node's val is an integer (can be negative)
• The random pointer can point to any node in the list or null
• The list can have 0 to 1000 nodes
• We assume that random pointers form valid references (no cycles in the original structure)
• The original list should remain unmodified

Data shape and hidden structure: The problem involves a singly-linked list with additional random pointer connections, creating what's essentially a graph structure where nodes can have multiple outgoing edges (next and random). The challenge lies in maintaining the topological relationship between nodes during deep copy.

The structure can be visualized as a directed graph where:

• Each node is a vertex
• next pointer represents one edge
• random pointer represents another edge (potentially to any node)
• The graph may have cycles in the random connections

2. Pattern Recognition

The problem involves creating a deep copy of a linked list where each node has a "random" pointer that can point to any node in the list (including itself) or be null.

Most likely patterns:

1. Hash Map + Two-Pass Algorithm - This is the most direct pattern for handling random pointers that can point to any node in the list
2. Interweaving/Splicing Technique - A clever approach that avoids hash maps by using the structure itself to maintain mapping

Wording that signals the pattern:

• "random pointer" - This indicates we need to handle a secondary pointer that doesn't follow the linear structure
• "deep copy" - This signals we must create entirely new nodes rather than reusing existing ones
• The constraint that random pointers can point to any node (including later nodes) suggests we need to handle forward references

Why this fits the pattern: The core challenge is that we cannot simply traverse the list once and create copies because random pointers might point to nodes that haven't been created yet. This creates a dependency issue that requires either:

1. A mapping mechanism to track already-created nodes, or
2. A clever restructure of the list that allows us to create mappings during traversal

Core insight: The key insight is that we need to break the dependency cycle between creating nodes and setting random pointers. This can be solved by either:

• Using a hash map to store the mapping from original nodes to their copies (O(n) space)
• Using an interweaving technique where we insert copy nodes between original nodes and then separate them (O(1) space but more complex)

The hash map approach is more intuitive and directly addresses the random pointer mapping problem, making it the preferred pattern for this type of list deep copy problem.

3. Approach Evolution

My first instinct is to create a deep copy of the linked list with random pointers, which seems like it could be solved by traversing the original list and creating new nodes. But that's O(n²) because for each node, I'd need to search through the entire original list to find the corresponding random pointer target. Let me think about how to optimize this.

I notice that if I maintain a mapping between original nodes and their copies, I can reduce it to O(n) by using a hash map to store the mapping. This way, when I encounter a random pointer, I can look up the copy of the target node in O(1) time instead of doing a linear search.

The key insight is to think of this as two phases: first pass creates all the new nodes and builds the mapping, second pass sets up all the pointers. This is a classic "two-pass" pattern that's very common in linked list problems.

Let me trace through this more carefully. I'll need to handle the random pointers correctly - they can point to any node in the original list, including nodes that come later or even earlier in the traversal. So I can't just process them in order.

The invariant I must maintain is that for any original node n, if n.random points to some node m, then in my copy, the corresponding new node n' must have its random pointer point to m' where m' is the copy of m.

I can approach this in two ways:

1. First pass: Create all new nodes and store mapping from original to copy
2. Second pass: Set up all next and random pointers using the mapping

This approach is clean, intuitive, and handles all edge cases properly. The time complexity becomes O(n) with a single pass for creating nodes and another for setting pointers, and space is O(n) for the hash map.

My approach is to use a HashMap to store the mapping between original nodes and their copies. This allows me to handle random pointers correctly by ensuring that when I create a new node, I can immediately look up any random pointer target in O(1) time. The two-pass strategy ensures I never try to reference a node that hasn't been created yet, which is the key optimization over naive approaches.

4. Data Structure Choice

For this problem, I need to choose data structures that will efficiently handle the copying of a linked list with random pointers while maintaining the correct relationships.

The primary data structure is a HashMap to store the mapping between original nodes and their copies. This is essential because:

• It allows O(1) lookup time when creating random pointer connections
• It prevents duplicate node creation by tracking which nodes have already been processed
• It enables us to handle cycles in the random pointer graph correctly

I'm using HashMap<Node, Node> where:

• Key: Original Node from the input list
• Value: Corresponding Copy Node in the new list

Why this choice is optimal: The HashMap approach is superior to alternatives like using a simple list or array because:

1. It provides constant-time node lookups by reference
2. It handles arbitrary random pointer connections without needing to traverse the entire list repeatedly
3. It naturally supports the recursive structure of the problem where we might encounter nodes in any order

Space considerations:

• The HashMap will store at most N entries where N is the number of nodes
• Space complexity: O(N) for the HashMap storage
• This is unavoidable since we must create N new nodes and track their relationships

Helper structure: I'm not using any additional helper data structures beyond the HashMap. The solution uses a simple iterative approach that processes each node once and maintains the mapping throughout.

This choice directly enables the clean O(n) time solution where each node is processed exactly once and random pointers are resolved using constant-time HashMap lookups.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works:

Input: [[7,null],[13,0],[11,4],[10,2],[1,0]] where each element represents [val, random_index]

Step 1: Create initial copies

• Original list: 7 → 13 → 11 → 10 → 1
• After first pass: 7' → 13' → 11' → 10' → 1'
• We create new nodes but don't link them yet

Step 2: Build mapping from original to new nodes

• Map original node with value 7 → new node with value 7
• Map original node with value 13 → new node with value 13
• Continue for all nodes

Step 3: Set up random pointers using the mapping

• Original node with value 7 has random pointer to null → new node with value 7 gets random pointer to null
• Original node with value 13 has random pointer to index 0 (value 7) → new node with value 13 gets random pointer to new node with value 7
• Original node with value 11 has random pointer to index 4 (value 1) → new node with value 11 gets random pointer to new node with value 1
• Continue for all nodes

Step 4: Return the head of new list

• Return reference to new node with value 7

The key insight is that we process the list in two passes: first to create all copies and build our mapping, then to properly set up the random pointers using that mapping. This ensures we don't miss any references that might point to nodes we haven't created yet.

The algorithm handles the random pointer challenge by using a hash map to maintain the mapping between original and new nodes, ensuring that when we set random pointers on new nodes, we're pointing to the correct new nodes rather than original ones.

6. Java Solution

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

public class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        
        // Step 1: Create a mapping from original nodes to their copies
        Map<Node, Node> nodeMap = new HashMap<>();
        
        // Step 2: First pass - create all copies without setting pointers
        Node current = head;
        while (current != null) {
            nodeMap.put(current, new Node(current.val));
            current = current.next;
        }
        
        // Step 3: Second pass - set next and random pointers for copies
        current = head;
        while (current != null) {
            Node copy = nodeMap.get(current);
            
            // Set next pointer
            if (current.next != null) {
                copy.next = nodeMap.get(current.next);
            }
            
            // Set random pointer
            if (current.random != null) {
                copy.random = nodeMap.get(current.random);
            }
            
            current = current.next;
        }
        
        // Return the copy of the head node
        return nodeMap.get(head);
    }
}

This solution uses a HashMap to maintain a mapping between original nodes and their copies. The approach involves two passes through the list: first to create all copies, then to establish the proper pointer connections. This ensures that when we set the random pointers in the second pass, all referenced nodes have already been created.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes exactly three passes through the list:

1. First pass: O(n) to create all new nodes and build the hash map
2. Second pass: O(n) to set up the next pointers
3. Third pass: O(n) to set up the random pointers

Since we're doing a constant amount of work for each node in each pass, and we process each node exactly once per pass, the total time complexity is O(3n) = O(n).

Space Complexity: O(n)

The space complexity comes from:

1. The hash map storing n node mappings: O(n)
2. The new list of n nodes: O(n)

Therefore, total space complexity is O(2n) = O(n).

Why these bounds are correct:

The bounds are tight because:

• We must process each node at least once to create the copy (Ω(n))
• We must store a mapping for each node (Ω(n))
• The hash map lookup is O(1) amortized, so the random pointer assignment is O(1) per node
• The algorithm scales linearly with input size

Optimality:

This is optimal for the problem as stated. We must read and process each node at least once, and we must store a mapping to handle the random pointers correctly. Any approach that doesn't process all nodes or doesn't store the required mapping would be incomplete and incorrect.

The solution achieves the theoretical lower bound of O(n) time and O(n) space for this problem, making it near-optimal. The linear scaling with input size is unavoidable given the requirement to create a complete independent copy of the list structure.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty list: Handle null input gracefully - the solution should return null without any operations
• Single node: Verify that both next and random pointers are properly handled for a single-node list
• Self-referencing: A node pointing to itself via random pointer (e.g., node.random = node) - this requires careful handling in the mapping to avoid infinite loops

Duplicate Values and Repeated States

• Duplicate values: Multiple nodes can have the same val - this should not affect copying logic as we're copying structure, not values
• Multiple nodes pointing to same random node: When several nodes point to the same random node, ensure that the copy maintains the same relative structure

Boundary Conditions

• Random pointer to null: Nodes may have random = null - ensure proper handling in mapping and copying
• Random pointer to a node that comes later: When random points to a node that hasn't been created yet in the copy, we must defer the assignment or handle it carefully
• Circular references: The random pointer can create cycles in the original list that must be preserved in the copy

Common Implementation Mistakes

• Not maintaining mapping consistency: When creating copies, ensure that each original node maps to exactly one copy node - reusing nodes or incorrect mapping leads to wrong structure
• Not handling cycles in random pointers: If random points to a node that will be created later, we must defer the assignment or use a two-pass approach
• Incorrect pointer assignment: Assigning random to the wrong copy node due to incorrect mapping or index-based assumptions
• Modifying original list: Accidentally modifying the input list during copying process - the original should remain unchanged
• Missing null checks: Failing to check for null before accessing node properties can cause NullPointerExceptions

Implementation-specific Pitfalls

• HashMap key equality: Using Node as a key in HashMap requires proper equals() and hashCode() implementation or using a wrapper approach to avoid incorrect mapping
• Order of operations: Creating all copies before assigning random pointers can cause issues when random points to nodes not yet created
• Memory leaks: Not properly managing references in the mapping structure that could prevent garbage collection

9. Alternative Approaches

There are several alternative approaches to solving the copy list with random pointer problem, each with different trade-offs:

1. Three-Pass Approach with HashMap Instead of the two-pass approach, we could use three passes:

• First pass: Create all new nodes and store mapping in HashMap
• Second pass: Set next pointers using the map
• Third pass: Set random pointers using the map

This approach is more intuitive but requires three iterations through the list and additional space for the mapping.

2. Recursive with Memoization We could use recursion with a HashMap to cache already-created nodes:

Map<Node, Node> visited = new HashMap<>();
Node copy = dfs(node);

The recursive approach has the advantage of naturally handling the random pointer connections but risks stack overflow for very long lists and requires additional space for the call stack.

3. Interweaving Technique (Space-Optimized) This approach modifies the original list temporarily:

1. Interweave original and copied nodes (A → A' → B → B')
2. Set random pointers for copied nodes
3. Separate the lists back

This approach uses O(1) extra space but modifies the input structure temporarily, which might not be acceptable in some contexts.

4. Hash Map with Node Identity Instead of using the node values as keys, we could use object identity or a custom hash function based on node position in the original list. This is more complex to implement and less reliable than using the actual node references.

The chosen two-pass approach with HashMap is preferred because it's clean, readable, and handles all edge cases properly while maintaining O(n) time and space complexity. The alternatives either increase space usage (three-pass), risk stack overflow (recursive), or require modifying the input structure (interweaving).

10. Test Cases

// Test case 1: Basic functionality with random pointers
// Input: [[7,null],[13,0],[11,4],[10,2],[1,0]]
// Expected: A deep copy where each node's random pointer points to the corresponding new node
@Test
public void testBasicFunctionality() {
    Node head = new Node(7);
    Node node2 = new Node(13);
    Node node3 = new Node(11);
    Node node4 = new Node(10);
    Node node5 = new Node(1);
    
    head.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    
    head.random = null;
    node2.random = head;  // 13's random points to 7
    node3.random = node5; // 11's random points to 1
    node4.random = node3; // 10's random points to 11
    node5.random = head;  // 1's random points to 7
    
    Node result = copyRandomList(head);
    assertNotNull(result);
    assertEquals(7, result.val);
    assertEquals(13, result.next.val);
    assertEquals(11, result.next.next.val);
    assertEquals(10, result.next.next.next.val);
    assertEquals(1, result.next.next.next.next.val);
    
    // Verify random pointers point to new nodes
    assertEquals(result.next.random, result);  // 13's random should point to new 7
    assertEquals(result.next.next.random, result.next.next.next); // 11's random should point to new 1
    assertEquals(result.next.next.next.random, result.next.next); // 10's random should point to new 11
    assertEquals(result.next.next.next.next.random, result); // 1's random should point to new 7
}

// Test case 2: Single node with self-reference
// Input: [[1,1]]
// Expected: Node with random pointer pointing to itself
@Test
public void testSingleNodeWithSelfReference() {
    Node head = new Node(1);
    head.random = head;  // Self reference
    
    Node result = copyRandomList(head);
    assertNotNull(result);
    assertEquals(1, result.val);
    assertEquals(result, result.random);  // Random should point to the new node
}

// Test case 3: Empty list
// Input: null
// Expected: null
@Test
public void testEmptyList() {
    assertNull(copyRandomList(null));
}

// Test case 4: List with cycles in random pointers
// Input: [[1,2],[2,3],[3,1]] - creating a cycle in random pointers
// Expected: Deep copy with same cycle structure in new list
@Test
public void testCycleInRandomPointers() {
    Node head = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    
    head.next = node2;
    node2.next = node3;
    node3.next = null;
    
    head.random = node3;   // 1's random points to 3
    node2.random = head;   // 2's random points to 1  
    node3.random = node2;  // 3's random points to 2
    
    Node result = copyRandomList(head);
    
    assertNotNull(result);
    assertEquals(1, result.val);
    assertEquals(2, result.next.val);
    assertEquals(3, result.next.next.val);
    
    // Verify random pointers form same cycle structure
    assertEquals(result.next.next.random, result);  // 3's random should point to new 1
    assertEquals(result.random, result.next);       // 1's random should point to new 2
    assertEquals(result.next.random, result.next.next); // 2's random should point to new 3
}

// Test case 5: All random pointers point to null
// Input: [[1,null],[2,null],[3,null]]
// Expected: Deep copy with all random pointers null
@Test
public void testAllRandomNull() {
    Node head = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    
    head.next = node2;
    node2.next = node3;
    
    Node result = copyRandomList(head);
    
    assertNotNull(result);
    assertEquals(1, result.val);
    assertEquals(2, result.next.val);
    assertEquals(3, result.next.next.val);
    
    assertNull(result.random);
    assertNull(result.next.random);
    assertNull(result.next.next.random);
}

11. Final Summary

The core idea is to create a deep copy of a linked list with random pointers by using a hash map to track the mapping between original and cloned nodes, ensuring that all references are properly maintained in the new structure. This solution works efficiently by making two passes through the list: first to create all nodes and build the mapping, then to set up all the random and next pointers correctly. The approach is optimal with O(n) time and space complexity, where n is the number of nodes in the list, making it well-suited for the constraints typically found in FAANG interviews.