Copy List with Random pointer

Problem Link

138. Copy List with Random Pointer – LeetCode

Problem Statement

A linked list is given where each node contains two pointers:

• next: points to the next node

• random: points to a random node (or null)

You must create a deep copy of the list.
Each node in the new list should have the same value and random pointer configuration but be entirely independent from the original list.

Examples

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]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Constraints

• 0 <= n <= 1000 where n is the number of nodes

• -10000 <= Node.val <= 10000

• Node.random may be null or pointing to any node in the list

• The list is guaranteed to be acyclic

Intuition

To copy the list with random pointers:

• You can't use the same node references.

• A naive approach uses a HashMap<Node, Node>, but it consumes extra space.

• The optimal in-place O(1) space solution interleaves new nodes with original nodes and then separates them.

Approach: Interleaving Nodes (O(1) space)

1. Interleave cloned nodes between original nodes.

2. Assign random pointers using original.random.next.

3. Separate the two lists into original and cloned.

Java Code

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

        // Step 1: Interleave copied nodes
        Node curr = head;
        while (curr != null) {
            Node copy = new Node(curr.val);
            copy.next = curr.next;
            curr.next = copy;
            curr = copy.next;
        }

        // Step 2: Assign random pointers
        Node orig = head;
        while (orig != null) {
            if (orig.random != null) {
                orig.next.random = orig.random.next;
            }
            orig = orig.next.next;
        }

        // Step 3: Detach copied list from original
        Node dummy = head.next;
        Node copyCurr = dummy;
        orig = head;
        while (orig != null) {
            orig.next = orig.next.next;
            if (copyCurr.next != null) {
                copyCurr.next = copyCurr.next.next;
            }
            orig = orig.next;
            copyCurr = copyCurr.next;
        }

        return dummy;
    }
}

Time and Space Complexity

Dry Run

Input:

1 → 2 → 3 → null
random: 1→3, 2→1, 3→2

Step 1:
Create interleaved list:

1 → 1' → 2 → 2' → 3 → 3'

Step 2:
Assign randoms:
1'.random = 3' (original 1's random → 3 → 3')
2'.random = 1'
3'.random = 2'

Step 3:
Split the lists.

Conclusion

This elegant O(1) space solution is a powerful trick in linked list cloning.
By interleaving and detaching, we avoid extra space while maintaining clean node relationships.