L27. Clone a LinkedList with Next and Random Pointers | Copy List with Random Pointers

1. Problem Statement & Initial Understanding

When copying a standard singly-linked list, the node structure contains only a value and a next pointer. However, in this advanced variant, each node contains a third pointer called a random pointer, which can point to any arbitrary node in the linked list or to null.

The Core Challenge

• A naive approach of copying a list node-by-node fails because when creating a node and assigning its random pointer, the target node of that random pointer might not yet exist in memory.
• We need to create an exact structural and relational replica (a deep copy) of the linked list and return the head of the newly created list.

2. Naive Approach: The Hash Map Strategy

To solve the dependency problem where random nodes might not yet be created, the most straightforward approach is to use a auxiliary Hash Map to track mapping between original nodes and their newly created copies.

Step-by-Step Execution

1. First Traversal (Node Creation & Mapping):
   • Traverse the original list from head to tail.
   • For every node encountered, create a deep copy containing only the copied value.
   • Store the relationship in a hash map as Map<Node, Node>, where the key is the original node and the value is the copied node.
2. Second Traversal (Pointer Wiring):
   • Traverse the original list a second time.
   • For every node, use the hash map to connect the copied node's next pointer to the copy of the original's next node.
   • Similarly, connect the copied node's random pointer to the copy of the original's random node (map.get(temp.random)).
3. Head Retrieval:
   • Return map.get(head), which gives the head of the newly copied list.

Pseudo-Code for Hash Map Approach

function copyRandomList(head: Node | null): Node | null {
    if (!head) return null;
    let map = new Map<Node, Node>();
    
    // Step 1: Create all nodes and store mapping
    let temp = head;
    while (temp !== null) {
        let newNode = new Node(temp.val);
        map.set(temp, newNode);
        temp = temp.next;
    }
    
    // Step 2: Connect next and random pointers
    temp = head;
    while (temp !== null) {
        let copyNode = map.get(temp)!;
        copyNode.next = map.get(temp.next!) || null;
        copyNode.random = map.get(temp.random!) || null;
        temp = temp.next;
    }
    
    // Step 3: Return head of copied list
    return map.get(head)!;
}

Complexity Analysis of Hash Map Approach

• Time Complexity: $O(2N) \approx O(N)$ because we traverse the linked list twice. (Assuming $O(1)$ hash map lookups).
• Space Complexity: $O(N)$ auxiliary space for storing all $N$ nodes inside the hash map, plus the $O(N)$ space required to build the new list itself.

3. The Interviewer's Constraint: Can We Optimize Space?

While the hash map approach is intuitive and works, interviewers typically ask: "Can we solve this without using $O(N)$ extra space for the hash map?"

Real-Life Analogy: Interleaving Paper Copies

Imagine you have a physical stack of documents where each page has notes pointing to other random pages. Instead of maintaining a separate notebook (hash map) to write down which page corresponds to which photocopy, you temporarily insert each fresh photocopy directly behind its original page in the exact same physical folder.

Now, every original page's immediate neighbor (temp.next) is its own photocopy! This eliminates the need for an external directory. Once you establish all the cross-references, you simply peel out the interleaved photocopies to restore the original document and finalize your cloned stack.

4. Optimized Three-Step In-Place Algorithm

To achieve $O(1)$ auxiliary space (excluding the memory required for the output list), we manipulate the list directly in three distinct phases.

Phase 1: Inserting Copy Nodes In-Between

We iterate through the original list, create a copy of each node, and insert that copy directly between the original node and its next neighbor.

Step-by-Step Mutation Logic:

1. Create copyNode = new Node(temp.val).
2. Point copyNode.next = temp.next.
3. Point temp.next = copyNode.
4. Advance pointer by two steps: temp = temp.next.next.

Pseudo-Code for Phase 1:

let temp = head;
while (temp !== null) {
    let copyNode = new Node(temp.val);
    copyNode.next = temp.next;
    temp.next = copyNode;
    temp = temp.next.next; // Move past the copy node
}

Phase 2: Connecting Random Pointers

Now that every original node is immediately followed by its clone (temp.next), we can easily determine the random pointer destination for the copy.

• If an original node's random pointer points to X, then the cloned node's random pointer (temp.next.random) should point to the clone of X, which is X.next.

Original Node: temp
Cloned Node:   temp.next
Random Target: temp.random
Clone of Target: temp.random.next

Edge Case Handling (null checks):

If an original node's random pointer is null, its clone's random pointer must also be null.

Pseudo-Code for Phase 2:

temp = head;
while (temp !== null) {
    if (temp.random !== null) {
        temp.next.random = temp.random.next;
    } else {
        temp.next.random = null;
    }
    temp = temp.next.next;
}

Phase 3: Restoring Original List & Extracting the Cloned List

In the final phase, we must disentangle our interleaved list. We separate the original linked list back to its pristine state while extracting the copied nodes into an independent linked list.

Step-by-Step Extraction Logic:

1. Initialize a dummyNode and a rest pointer to build the cloned list.
2. Traverse with temp starting at head.
3. Link the cloned node to our extraction list: rest.next = temp.next.
4. Restore the original list's next pointer: temp.next = temp.next.next.
5. Advance both pointers: rest = rest.next, temp = temp.next.

Pseudo-Code for Phase 3:

let dummyNode = new Node(-1);
let rest = dummyNode;
let temp = head;

while (temp !== null) {
    // Extract the copy node
    rest.next = temp.next;
    rest = rest.next;
    
    // Restore the original list's next pointer
    temp.next = temp.next.next;
    
    // Move temp forward
    temp = temp.next;
}

let clonedHead = dummyNode.next;

5. Comprehensive Summary Table

Summary and Key Takeaways

• The Core Obstacle: Standard deep copy approaches fail for random pointers because destination nodes may not yet exist when copying begins.
• Mental Model (Interleaving): Placing cloned nodes directly after their originals turns temp.next into an instant lookup reference for cloned counterparts.
• Phase 1 (Insertion): Create deep copy nodes and weave them directly into the original linked list sequence.
• Phase 2 (Random Wiring): Leverage the interleaved structure to wire up random pointers using temp.next.random = temp.random.next.
• Phase 3 (Decoupling & Restoration): Unweave the interleaved structure to restore the original linked list while isolating the newly minted copy list.
• Edge Cases: Always explicitly check for null random pointers before attempting to access temp.random.next.
• Time Complexity: The optimized in-place algorithm runs in $O(3N) \approx O(N)$ time across its three discrete traversals.
• Space Complexity: Auxiliary space is reduced to $O(1)$ (not counting the memory required by the problem statement to return the final cloned list).