Copy List With Random Pointer – 138. LeetCode

This problem involves copying a linked list where each node contains:

1. A next pointer pointing to the next node in the sequence.

2. A random pointer pointing to any node in the list, or null.

The challenge is to create an identical copy of the list, including the random pointers, without modifying the original. This requires both deep copying and preserving the relationships between the nodes.

Brute Force Approach

A brute force solution could involve:

1. Iterating through the original list to create a copy of each node.

2. Using another loop to set the random pointers in the copied list by mapping original nodes to copied nodes.

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

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

        Node curr = head;
        while (curr != null) {
            map.put(curr, new Node(curr.val)); // Create copy of each node
            curr = curr.next;
        }

        curr = head;
        while (curr != null) {
            map.get(curr).next = map.get(curr.next); // Set next pointers
            map.get(curr).random = map.get(curr.random); // Set random pointers
            curr = curr.next;
        }

        return map.get(head);
    }
}

Optimized Approach: Constant Space Solution

This optimized approach modifies the original list temporarily:

1. Insert cloned nodes directly after their originals.

2. Assign the random pointers for the cloned nodes.

3. Separate the original and cloned lists.

This achieves O(1) space complexity by avoiding auxiliary data structures like hashmaps.

The key idea is to leverage the existing structure of the linked list to maintain relationships between nodes. By interleaving original and cloned nodes, we preserve the random pointer connections without needing extra memory.

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

        // Step 1: Interleave 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
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }

        // Step 3: Separate the lists
        Node dummy = new Node(0);
        Node copyCurr = dummy;
        curr = head;

        while (curr != null) {
            Node copy = curr.next;
            copyCurr.next = copy;
            copyCurr = copy;

            curr.next = copy.next; // Restore original list
            curr = curr.next;
        }

        return dummy.next;
    }
}

Step 1: Interleave Nodes

Node curr = head;
while (curr != null) {
    Node copy = new Node(curr.val);
    copy.next = curr.next;
    curr.next = copy;
    curr = copy.next;
}

• This loop creates a new node for each original node and places it after the original node in the list.
• By interleaving the nodes, the random pointers of the copied nodes can easily be set in the next step using the original nodes random pointers.

Step 2: Assign Random Pointers

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

• Sets the random pointer of each copied node to the copied version of the node pointed to by curr.random.
• Skips the copied node and moves to the next original node.

Step 3: Seperate the Lists

Node dummy = new Node(0);
Node copyCurr = dummy;
curr = head;

• Using a dummy node ensures uniform handling of edge cases (like an empty or single-node list).
• copyCurr is a pointer that will help build the new list by moving through the dummy node’s chain.
• curr starts at head and traverses the original list.

Step 4: Restore Original List

while (curr != null) {
    Node copy = curr.next;
    copyCurr.next = copy;
    copyCurr = copy;

    curr.next = copy.next; // Restore the original list
    curr = curr.next;
}

• Iterates through the original list one node at a time until curr becomes null (end of the list).

• Extract the copied node.
• Link copied node to new list.
• Reconnect the original node to its next original node, effectively removing the interleaved copied nodes.

Step 5: Move to the Next Node in the Original List

curr = curr.next;

• Advances the curr pointer to the next original node.

Step 6: Return

return dummy.next;

• Returns the copied list starting from the first copied node (dummy.next).

Why This Code Works

Using this method ensures:

1. The original structure is respected and restored.

2. The copied list maintains the deep copy requirement.

3. Traversal and splitting occur in one linear pass for O(n) time complexity.

This approach demonstrates careful planning of traversal patterns and efficient reuse of existing structures.