Copy List with Random Pointer

Problem Statement

You are given a linked list where each node has two pointers: next (pointing to the next node) and random (pointing to any node in the list or null). Construct a deep copy of the list. The new list must use entirely new nodes, and the next and random pointers of the new nodes must reflect the same structure as the original.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Explanation: Each pair is [val, random_index]. Node 1 (val=13) has random 
pointing to node 0 (val=7). The deep copy preserves this structure.

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Explanation: Both nodes' random pointers point to node 1 (val=2).

Constraints:

• 0 <= n <= 1000
• -10^4 <= Node.val <= 10^4
• random points to a node in the list or is null.

Difficulty: Medium (LC 138)

---

Pattern Recognition

• What is the input structure? A linked list with an additional random pointer creating a graph-like structure.
• What are we optimizing? Creating a deep copy while correctly mapping random pointers from old nodes to new nodes.
• What pattern does this fit? Node cloning with reference mapping. The core challenge is mapping original nodes to their copies so that random pointers can be set correctly.
• Why does this pattern fit? The next pointers define a simple linked list (easy to copy), but random pointers can point anywhere, requiring a way to look up "given this original node, what is its copy?"

---

Approach

Approach 1 — HashMap (Two Pass)

Use a hash map to store the mapping from original nodes to their copies.

Pass 1: Create a copy of each node (without setting pointers). Store original → copy in a map.
Pass 2: Set next and random pointers using the map.

Time: O(n) — two passes through the list. Space: O(n) — the hash map.

Approach 2 — Recursive with Memoization

Clone nodes recursively, using a memo dict to avoid duplicating nodes.

Time: O(n). Space: O(n) — memo dict + recursion stack.

Approach 3 — Optimal: Interleaving Nodes (O(1) Space)

Key Insight: Instead of a hash map, interleave copied nodes directly into the original list. For each original node A, insert its copy A' immediately after it: A → A' → B → B' → C → C'. Now A.random.next is the copy of A.random. This eliminates the need for a hash map.

Step-by-step:

1. Interleave: For each node A, create A' and insert it after A. The list becomes A → A' → B → B' → ...
2. Set random pointers: For each original node A, set A'.random = A.random.next (which is the copy of A.random).
3. Separate lists: Extract the copied nodes into their own list and restore the original list.

function copyRandomList(head):
    # Step 1: Interleave
    curr = head
    while curr:
        copy = new Node(curr.val)
        copy.next = curr.next
        curr.next = copy
        curr = copy.next

    # Step 2: Set random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next

    # Step 3: Separate
    curr = head
    copyHead = head.next if head else None
    while curr:
        copy = curr.next
        curr.next = copy.next
        copy.next = copy.next.next if copy.next else None
        curr = curr.next
    return copyHead

Time: O(n) — three passes. Space: O(1) — no extra data structures (the copied nodes are the output, not extra space).

---

Walkthrough

Original list: 7 → 13 → 11 → 10 → 1 Random pointers: 7→null, 13→7, 11→1, 10→11, 1→7

Step 1 — Interleave:

7 → 7' → 13 → 13' → 11 → 11' → 10 → 10' → 1 → 1'

Operation	List state
Insert 7' after 7	7 → 7' → 13 → 11 → 10 → 1
Insert 13' after 13	7 → 7' → 13 → 13' → 11 → 10 → 1
Insert 11' after 11	7 → 7' → 13 → 13' → 11 → 11' → 10 → 1
Insert 10' after 10	... → 10 → 10' → 1
Insert 1' after 1	... → 1 → 1' → None

Step 2 — Set random pointers:

Node	random	random.next (= copy of random)	Copy's random
7	null	—	7'.random = null
13	7	7'	13'.random = 7'
11	1	1'	11'.random = 1'
10	11	11'	10'.random = 11'
1	7	7'	1'.random = 7'

Step 3 — Separate:

Extract: 7' → 13' → 11' → 10' → 1' Restore: 7 → 13 → 11 → 10 → 1

---

Implementation

Approach 1 — HashMap

TypeScript

class Node {
    val: number;
    next: Node | null;
    random: Node | null;

    constructor(val = 0, next: Node | null = null, random: Node | null = null) {
        this.val = val;
        this.next = next;
        this.random = random;
    }
}

function copyRandomListHashmap(head: Node | null): Node | null {
    if (!head) return null;

    // Pass 1: Create copies and build old → new mapping
    const oldToNew = new Map<Node, Node>();
    let curr: Node | null = head;
    while (curr) {
        oldToNew.set(curr, new Node(curr.val));
        curr = curr.next;
    }

    // Pass 2: Set next and random pointers
    curr = head;
    while (curr) {
        const copy = oldToNew.get(curr)!;
        copy.next = oldToNew.get(curr.next!) ?? null;
        copy.random = oldToNew.get(curr.random!) ?? null;
        curr = curr.next;
    }

    return oldToNew.get(head)!;
}

C++

struct Node {
    int val;
    Node* next;
    Node* random;
    Node(int v = 0, Node* n = nullptr, Node* r = nullptr)
        : val(v), next(n), random(r) {}
};

Node* copyRandomListHashmap(Node* head) {
    if (!head) return nullptr;

    // Pass 1: Create copies and build old → new mapping
    unordered_map<Node*, Node*> oldToNew;
    Node* curr = head;
    while (curr) {
        oldToNew[curr] = new Node(curr->val);
        curr = curr->next;
    }

    // Pass 2: Set next and random pointers
    curr = head;
    while (curr) {
        Node* copy = oldToNew[curr];
        copy->next = oldToNew.count(curr->next) ? oldToNew[curr->next] : nullptr;
        copy->random = oldToNew.count(curr->random) ? oldToNew[curr->random] : nullptr;
        curr = curr->next;
    }

    return oldToNew[head];
}

Approach 3 — Interleaving (O(1) Space)

TypeScript

function copyRandomList(head: Node | null): Node | null {
    if (!head) return null;

    // Step 1: Interleave — insert copy after each original node
    let curr: Node | null = head;
    while (curr) {
        const copy = new Node(curr.val);
        copy.next = curr.next;
        curr.next = copy;
        curr = copy.next; // Move to next original node
    }

    // Step 2: Set random pointers for copies
    curr = head;
    while (curr) {
        if (curr.random) {
            curr.next!.random = curr.random.next;
        }
        curr = curr.next!.next; // Skip over copy to next original
    }

    // Step 3: Separate the two lists
    const copyHead = head.next!;
    curr = head;
    while (curr) {
        const copy = curr.next!;
        curr.next = copy.next;              // Restore original list
        copy.next = copy.next?.next ?? null; // Link copies
        curr = curr.next;                   // Move to next original
    }

    return copyHead;
}

C++

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;

    // Step 1: Interleave — insert copy after each original node
    Node* curr = head;
    while (curr) {
        Node* copy = new Node(curr->val);
        copy->next = curr->next;
        curr->next = copy;
        curr = copy->next; // Move to next original node
    }

    // Step 2: Set random pointers for copies
    curr = head;
    while (curr) {
        if (curr->random) {
            curr->next->random = curr->random->next;
        }
        curr = curr->next->next; // Skip over copy to next original
    }

    // Step 3: Separate the two lists
    Node* copyHead = head->next;
    curr = head;
    while (curr) {
        Node* copy = curr->next;
        curr->next = copy->next;                           // Restore original list
        copy->next = copy->next ? copy->next->next : nullptr; // Link copies
        curr = curr->next;                                 // Move to next original
    }

    return copyHead;
}

Watch out:

1. Null pointer errors in Step 3. When separating, copy.next might be None (last copy node). Always check before accessing .next.
2. Forgetting to handle random = null. In Step 2, only set curr.next.random when curr.random is not None. Otherwise you will get a NullPointerException.
3. Not restoring the original list. The interleaving approach modifies the original list. If the interviewer expects the original to be unchanged, Step 3 must fully restore it. Verify by checking that head still works after the function returns.

---

Complexity Analysis

	Time	Space
HashMap (Approach 1)	O(n)	O(n)
Recursive + Memo (Approach 2)	O(n)	O(n)
Interleaving (Approach 3)	O(n)	O(1)

Bottleneck: You must visit each node to copy it, so O(n) time is optimal. The space bottleneck is the hash map in Approaches 1-2. The interleaving approach eliminates this by using the list structure itself as the mapping.

---

Edge Cases

1. Empty list (head = None) — Return None immediately.
2. Single node — Copy the node. If random points to itself, the copy's random must point to the copy (not the original).
3. All random pointers are null — Degenerates to a simple linked list copy. Verify Step 2 handles this gracefully.
4. All random pointers point to the head — All copies' random must point to the copy of the head. Tests the mapping correctness.
5. Random pointer forms a cycle — E.g., A.random = B, B.random = A. The copy must mirror this without creating cross-references to original nodes.
6. Large list (n = 1000) — No algorithmic concern, but stack depth matters for the recursive approach.

---

Related Problems

• LC 133 — Clone Graph — Same pattern: deep copy a graph with arbitrary edges. Uses HashMap + BFS/DFS.
• LC 1485 — Clone Binary Tree With Random Pointer — Same cloning pattern applied to a tree.
• LC 382 — Linked List Random Node — Different problem but involves linked lists with randomness (reservoir sampling).
• LC 141 — Linked List Cycle — Floyd's cycle detection. Shares the "in-place linked list manipulation" skill.

---

What is Expected at Each Level

Junior: Implement the HashMap approach. Understand why you need a mapping from old to new nodes. Handle null pointers.

Mid-level: Write the HashMap solution cleanly. Know the interleaving approach and implement it with guidance. Discuss trade-offs between O(n) space and O(1) space.

Senior: Implement the interleaving approach from scratch without errors. Discuss restoring the original list. Extend to graph cloning (LC 133). Mention the recursive approach as an alternative. Discuss thread-safety concerns if the original list is shared.