Understanding Deep Copy vs Shallow Copy

A shallow copy duplicates only the top-level structure. For a linked list node A, its shallow copy A' would still reference the original node's next and random pointers. Any modifications to the original list would affect the copied version.

A deep copy creates an entirely independent replica. The new list allocates fresh nodes with identical values, and all pointers reference nodes within the new list itself, ensuring complete isolation from the original.

Algorithm: Interleaved Node Insertion

The optimal approach avoids hash maps by weaving copied nodes directly into the original list. This three-phase process runs in O(n) time with O(1) auxiliary space.

Phase 1: Node Replication and Interleaving

Traverse the original list, inserting a clone of each node immediately after it. For a list 1→2→3, the result becomes 1→1'→2→2'→3→3'.

Node current = head;
while (current != null) {
    Node clone = new Node(current.val);
    clone.next = current.next;
    current.next = clone;
    current = clone.next;
}

Phase 2: Mirroring Random Pointers

Each clone's random pointer should reference the cloned version of its original's random target. Since clones sit immediately after their originals, original.random.next points to the desired clone.

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

Phase 3: List Separation

Decouple the interleaved list into two independent lists. Use two pointers: one reconstructs the original list, the other builds the copy.

Node copiedHead = head.next;
Node copiedCurrent = copiedHead;
Node originalCurrent = head;

while (originalCurrent != null) {
    originalCurrent.next = copiedCurrent.next;
    originalCurrent = originalCurrent.next;
    
    if (originalCurrent != null) {
        copiedCurrent.next = originalCurrent.next;
        copiedCurrent = copiedCurrent.next;
    }
}

The conditional check if (originalCurrent != null) prevents a NullPointerException. When processing the final original node, its next becomes null (the original tail's original state), leaving the last copied node's next correctly set to null from the initial interleaving phase.

Complete Java Implementation

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        // Phase 1: Interleave cloned nodes
        Node current = head;
        while (current != null) {
            Node clone = new Node(current.val);
            clone.next = current.next;
            current.next = clone;
            current = clone.next;
        }

        // Phase 2: Assign random pointers for clones
        current = head;
        while (current != null) {
            if (current.random != null) {
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }

        // Phase 3: Separate the two lists
        Node copiedHead = head.next;
        Node copiedCurrent = copiedHead;
        current = head;

        while (current != null) {
            current.next = copiedCurrent.next;
            current = current.next;
            
            if (current != null) {
                copiedCurrent.next = current.next;
                copiedCurrent = copiedCurrent.next;
            }
        }

        return copiedHead;
    }
}

Common Pitfall: Misusing Head Pointers

During list separation, a frequent mistake involves using the head pointer as an iterator instead of a dedicated traversal variable:

// Incorrect approach
Node copiedHead = head.next;
Node copiedCurrent = copiedHead;
current = head;

while (current != null) {
    current.next = copiedHead.next;  // Wrong: should use copiedCurrent
    current = current.next;
    if (current != null) {
        copiedHead.next = current.next;  // Wrong: modifies head reference
        copiedHead = copiedHead.next;    // Wrong: loses head position
    }
}
return copiedHead;  // Returns tail instead of head

This error causes copiedHead to advance through the list, ultimately pointing to the tail node. The correct pattern maintains copiedHead as a fixed reference to the list's start while copiedCurrent handles traversal and linking.