Solving Copy List with Random Pointer in Python: Step-by-Step Guide

Introduction to Copy List with Random Pointer

The "Copy List with Random Pointer" problem is a classic algorithmic challenge frequently encountered in coding interviews and data structure courses. The task involves creating a deep copy of a linked list where each node contains not only a next pointer but also a random pointer that can point to any node in the list or be null. Unlike a shallow copy, a deep copy requires constructing entirely new nodes with the same structure, ensuring that modifications to the original list do not affect the copied one.

This problem tests your understanding of linked list traversal, pointer manipulation, and hash-based mapping strategies. In this tutorial, we will explore what the problem is, why it matters, multiple approaches to solve it, and best practices to write clean, efficient Python code.

What Is the Copy List with Random Pointer Problem?

Consider a singly linked list where each node has two pointers: next, which points to the subsequent node, and random, which can point to any node in the list (including itself) or be null. The goal is to produce a brand-new list that is structurally identical to the original, with every next and random pointer correctly replicated.

Node Definition

Before diving into solutions, let's define the node class that represents each element in the list:

class Node:
    def __init__(self, val=0, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

Each node stores an integer value, a reference to the next node, and a reference to a random node. The challenge arises because when you create a new node, you may not yet have created the node that its random pointer should reference.

Example Scenario

Imagine a list with three nodes: A (val=7), B (val=13), and C (val=11). Node A's random pointer is null, B's random points to A, and C's random points to C itself. A correct deep copy must reproduce this exact configuration with new node instances.

Why This Problem Matters

This problem is more than an academic exercise. It appears frequently in technical interviews at major tech companies because it evaluates several core competencies simultaneously:

Pointer manipulation: You must carefully manage references without creating cycles or memory leaks.
Graph traversal intuition: The random pointers effectively turn the list into a graph, requiring careful traversal.
Space-time tradeoffs: Different solutions offer different balances between memory usage and runtime.
Edge case handling: Empty lists, single-node lists, and self-referencing random pointers all need consideration.

In real-world applications, deep copying complex data structures is essential for features like undo/redo systems, serialization, and snapshot-based state management. Understanding this problem builds a foundation for handling more intricate object graph duplication tasks.

Approach 1: Hash Map Based Solution

The most intuitive approach uses a hash map (dictionary in Python) to store the mapping between original nodes and their copies. This allows you to look up the corresponding copied node whenever you need to set a next or random pointer.

Algorithm Steps

First pass: iterate through the original list and create a copy of each node, storing the mapping in a dictionary.
Second pass: iterate again and assign next and random pointers using the dictionary to find the corresponding copied nodes.

Implementation

def copyRandomList(head):
    if not head:
        return None

    # Step 1: Create a mapping from original nodes to copied nodes
    mapping = {}
    current = head
    while current:
        mapping[current] = Node(current.val)
        current = current.next

    # Step 2: Assign next and random pointers
    current = head
    while current:
        if current.next:
            mapping[current].next = mapping[current.next]
        if current.random:
            mapping[current].random = mapping[current.random]
        current = current.next

    return mapping[head]

Complexity Analysis

This solution runs in O(n) time, where n is the number of nodes, because we traverse the list twice. The space complexity is also O(n) due to the hash map storing all node mappings. This is a clean, readable solution that works well in most scenarios.

Approach 2: Interweaving Nodes (O(1) Space)

If you want to optimize space, you can avoid the hash map entirely by interweaving copied nodes between the original nodes. This approach modifies the original list temporarily but restores it afterward.

Algorithm Steps

First pass: insert a copy of each node immediately after the original node, creating an interweaved list.
Second pass: set the random pointers of the copied nodes by leveraging the interweaved structure.
Third pass: separate the interweaved list back into the original list and the copied list.

Implementation

def copyRandomList(head):
    if not head:
        return None

    # Step 1: Insert copied nodes after each original node
    current = head
    while current:
        new_node = Node(current.val)
        new_node.next = current.next
        current.next = new_node
        current = new_node.next

    # Step 2: Set random pointers for copied nodes
    current = head
    while current:
        if current.random:
            current.next.random = current.random.next
        current = current.next.next

    # Step 3: Separate the two lists
    current = head
    copy_head = head.next
    while current:
        copy = current.next
        current.next = copy.next
        if copy.next:
            copy.next = copy.next.next
        current = current.next

    return copy_head

Complexity Analysis

This approach still runs in O(n) time but reduces space complexity to O(1) (excluding the output list). The tradeoff is that the code is more complex and temporarily mutates the input list, which may not be desirable in all contexts.

Approach 3: Recursive Solution with Memoization

A recursive approach can also solve this problem elegantly. By using memoization, you ensure that each node is only copied once, even if multiple random pointers reference it.

Implementation

def copyRandomList(head):
    memo = {}

    def clone(node):
        if not node:
            return None
        if node in memo:
            return memo[node]

        # Create a new node and store it in memo before recursing
        new_node = Node(node.val)
        memo[node] = new_node

        new_node.next = clone(node.next)
        new_node.random = clone(node.random)

        return new_node

    return clone(head)

This solution is concise and mirrors the recursive structure of the problem. However, deep recursion on very long lists may hit Python's recursion limit, so it is best suited for moderately sized inputs.

Testing Your Solution

Writing tests is crucial to verify correctness. Below is a helper function to build a list from a list of tuples, along with test cases:

def build_list(data):
    if not data:
        return None
    nodes = [Node(val) for val, _ in data]
    for i, (_, rand_idx) in enumerate(data):
        if i < len(nodes) - 1:
            nodes[i].next = nodes[i + 1]
        if rand_idx is not None:
            nodes[i].random = nodes[rand_idx]
    return nodes[0]

def list_to_tuples(head):
    result = []
    index_map = {}
    current = head
    idx = 0
    while current:
        index_map[current] = idx
        current = current.next
        idx += 1
    current = head
    while current:
        rand_idx = index_map.get(current.random) if current.random else None
        result.append((current.val, rand_idx))
        current = current.next
    return result

# Test case
data = [(7, None), (13, 0), (11, 2), (10, 0), (1, 0)]
original = build_list(data)
copied = copyRandomList(original)
print(list_to_tuples(copied))
# Expected output: [(7, None), (13, 0), (11, 2), (10, 0), (1, 0)]

Always test edge cases such as an empty list, a single node with a self-referencing random pointer, and a list where all random pointers are null.

Best Practices

Handle the empty list first: Always check if head is None at the start to avoid unnecessary work and errors.
Choose readability over micro-optimizations: The hash map approach is easier to understand and maintain. Use the interweaving approach only when space is a proven constraint.
Avoid mutating the input: If you use the interweaving approach, ensure you fully restore the original list before returning.
Watch for recursion limits: The recursive solution is elegant but can fail on very long lists. Consider increasing sys.setrecursionlimit or switching to an iterative approach.
Write comprehensive tests: Include edge cases like self-loops, null random pointers, and single-node lists to ensure robustness.
Use clear variable names: Names like mapping, copy_head, and new_node make the code self-documenting.

Common Pitfalls

One frequent mistake is trying to set the random pointer before the target node has been created. This is why the hash map approach separates node creation from pointer assignment into two passes. Another common error in the interweaving approach is forgetting to restore the original list's next pointers, which can corrupt the input data.

Additionally, be careful when comparing nodes. Since you are creating new node instances, identity comparison (is) rather than equality comparison should be used when checking pointer relationships.

Conclusion

The Copy List with Random Pointer problem is a valuable exercise in pointer manipulation, graph traversal, and space-time tradeoff analysis. Whether you choose the straightforward hash map approach, the space-optimized interweaving technique, or the elegant recursive solution, understanding all three methods deepens your problem-solving toolkit. By following the best practices outlined in this tutorial and testing thoroughly against edge cases, you will be well-equipped to tackle this problem confidently in interviews and real-world applications alike.