Copy List with Random Pointer

Imagine having a linked list where each node has two pointers — one to the next node and another pointing randomly to any other node or even null. That’s what makes this problem interesting. This article explains the Copy List with Random Pointer problem clearly, using real-world logic, clean examples, and optimized solutions — all without overwhelming you.

Whether you're preparing for interviews or building your understanding of data structure, this problem is a great way to practice linked list cloning, node duplication, and pointer references in one go.

We’ll cover everything:

• What this problem means
• Why it’s tricky at first
• How hashing techniques help
• And how to clone without using extra memory

Let’s dive into it.

What Is the “Copy List with Random Pointer” Problem?

This problem deals with a special kind of linked list. Each node contains:

• A value,
• A next pointer to the next node,
• A random pointer that can point to any node in the list or null.

Your task is to clone the entire list. But not just a shallow copy — every node must be a new node, and the random connections must work exactly like in the original.

This is where node duplication, proper pointer references, and careful memory management come into play.

Why Is This Problem Challenging?

At first glance, you might think cloning each node and connecting them is easy. But the tricky part is keeping the random pointers accurate in the new list. You can't simply copy values; you have to carefully recreate relationships between nodes.

Some challenges:

• How do you track where random is pointing?
• How do you map old nodes to new ones?
• Can you solve it without using extra space?

To solve this, we’ll explore two clear approaches — one using a hash map implementation and one with pure algorithm optimization.

Approach 1: Use Hash Map to Track Node Mapping

This is a clean and simple approach using a hashing technique. We map each original node to its copied version. Then we use that mapping to assign both next and random pointers correctly.

How It Works:

1. Traverse the original list.
2. For each node, create a copy and store it in a hash map where the key is the original node and the value is the new one.
3. Traverse again to assign the next and random pointers for each copied node using this map.

Code Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def copyRandomList(head):
    if not head:
        return None

    node_map = {}
    current = head

    # Step 1: Node duplication
    while current:
        node_map[current] = Node(current.val)
        current = current.next

    # Step 2: Pointer references
    current = head
    while current:
        node_map[current].next = node_map.get(current.next)
        node_map[current].random = node_map.get(current.random)
        current = current.next

    return node_map[head]

Why This Works:

• Easy to understand and debug.
• Ensures correct node mapping.
• Great if you're just starting with linked list cloning.

Approach 2: Optimized Without Extra Space

Want to do better? This approach uses no extra space (except for the new nodes). It relies on weaving copied nodes into the original list and then separating them at the end.

How It Works:

1. For each node in the original list, create a copy and insert it right after the original.
2. Assign random pointers for the copied nodes using the interleaved structure.
3. Detach the copied list from the original.

Code Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def copyRandomList(head):
    if not head:
        return None

    current = head

    # Step 1: Interleave copy nodes
    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
    current = head
    while current:
        if current.random:
            current.next.random = current.random.next
        current = current.next.next

    # Step 3: Detach copied list
    original = head
    copy = head.next
    copy_head = copy

    while original:
        original.next = original.next.next
        if copy.next:
            copy.next = copy.next.next
        original = original.next
        copy = copy.next

    return copy_head

Why This Works:

• No need for a hash map.
• Efficient memory management.
• Better in terms of algorithm optimization.

Complexity Breakdown Without a Table

In the first approach, where we use a hash map, both time and space complexity are proportional to the number of nodes in the list. This is great for clarity but not space-efficient.

In the second approach, time complexity stays the same, but space complexity drops since we don’t store extra mappings. This makes it ideal when memory usage matters.

Conclusion

If you're serious about improving your data structure skills, this problem is a must-practice. It helps you learn:

• How to handle pointer references
• When to apply a hashing technique
• How to clone structures accurately using node duplication
• What makes an approach better in terms of complexity analysis

Start with the map-based method to build confidence. Then level up to the space-optimized version. You’ll not only master linked list cloning, but also get more comfortable with low-level memory management and smarter algorithm optimization.