Copy List With Random Pointer: Interleave Clones or HashMap

• Deep copy – create brand-new nodes whose next and random pointers point only into the copy, never into the original.
• HashMap approach – two passes: first creates clones and maps original->clone; second wires next and random via lookup.
• Interleaving approach – three passes: insert clones after originals, fix random pointers using adjacency, unweave into two separate lists.
• HashMap complexity – O(n) time, O(n) space.
• Interleaving complexity – O(n) time, O(1) extra space.

What is the problem?

Deep-copy a linked list where each node has a next pointer and a random pointer that can point to any node or null. The copy must mirror the structure but reference only copied nodes.

At the National Bank of India, loan records form a linked chain where each record also cross-references a guarantor. For archiving, the bank needs an independent copy.

Why is the random pointer tricky?

The next pointers can be copied in a simple left-to-right pass. But the random pointer may point forward to a node that has not been cloned yet, or backward to an already-cloned node. You need a way to look up the clone of any original node.

How does the HashMap approach work?

Two passes. First pass creates clones. Second pass wires pointers.

package com.bank.service;

import java.util.HashMap;
import java.util.Map;

public class CopyListWithRandom {
    public static Node copyRandomList(Node head) {
        if (head == null) return null;

        Map<Node, Node> map = new HashMap<>();

        // Pass 1: Create clones
        Node curr = head;
        while (curr != null) {
            map.put(curr, new Node(curr.val));
            curr = curr.next;
        }

        // Pass 2: Wire next and random
        curr = head;
        while (curr != null) {
            map.get(curr).next = map.get(curr.next);
            map.get(curr).random = map.get(curr.random);
            curr = curr.next;
        }

        return map.get(head);
    }
}

The convenience of map.get(null) returning null handles end-of-list and null random pointers with zero special cases.

How does the interleaving approach work?

Three passes. Insert clones, fix random, unweave.

package com.bank.service;

public class CopyListInterleave {
    public static Node copyRandomList(Node head) {
        if (head == null) return null;

        // Pass 1: Insert clone after each original
        Node curr = head;
        while (curr != null) {
            Node clone = new Node(curr.val);
            clone.next = curr.next;
            curr.next = clone;
            curr = clone.next;
        }

        // Pass 2: Set random for each clone
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }

        // Pass 3: Unweave into two lists
        Node copyHead = head.next;
        curr = head;
        Node copyCurr = copyHead;
        while (curr != null) {
            curr.next = copyCurr.next;
            curr = curr.next;
            if (curr != null) {
                copyCurr.next = curr.next;
                copyCurr = copyCurr.next;
            }
        }

        return copyHead;
    }
}

Why does interleaving make random pointer assignment easy?

After inserting clones, the clone of any node is always node.next. So to set the clone's random pointer, we do clone.random = original.random.next, because the clone of the random target is right after the target.

Before interleave:
  A -> B -> C
  A.random = C

After interleave:
  A -> A' -> B -> B' -> C -> C'

Setting A'.random:
  A.random = C, so A'.random = C.next = C'

What is the time and space complexity?

| Approach | Time | Space |
|---|---|---|
| HashMap | O(n) | O(n) |
| Interleaving | O(n) | O(1) extra |

Both create n new nodes (the copy), but the HashMap also stores n map entries.

What are common mistakes?

In the interleaving approach, forgetting to properly unweave the lists, leaving the original list corrupted.

// Wrong: original list is still interleaved with clones
// A -> A' -> B -> B' -> C -> C'

// Correct: restore original
// A -> B -> C  and  A' -> B' -> C'

In the HashMap approach, using new Node(curr.val) without adding the entry to the map.

What are the edge cases?

• Null head: return null.
• Single node with random pointing to itself: the clone's random must point to the clone, not the original.
• All random pointers are null: only next pointers need wiring.
• Random pointer creates a cycle: the copy must reproduce the same cycle structure.

What should a senior engineer know?

In practice, prefer the HashMap approach for its clarity and lower bug risk. The interleaving approach is elegant but the pointer surgery in the unweave step is error-prone under interview pressure.

The correctness requirement is that no pointer in the copy references any original node. In banking systems, this prevents a later edit to live data from silently mutating an archived record.

What are common interview follow-up questions?

• Which approach would you use in production? (HashMap for clarity.)
• What if the list is very long and memory is constrained? (Interleaving saves the map's O(n) space.)
• How would you test that the copy is truly independent? (Modify the original and verify the copy is unchanged.)