138. Copy List with Random Pointer

Intuition

To create a deep copy of a linked list where each node has both next and random pointers, we need to

1. Copy the nodes and their values.

2. Ensure the next pointers are maintained in order.

3. Correctly assign random pointers in the new list to the copied equivalents, not the originals.

To map original nodes to their copies (so we can later assign random pointers), we use a HashMap.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(N)$

Code

public Node copyRandomList(Node originalHead) {
    // Edge case: if the original list is empty, return null
    if (originalHead == null) return null;
    
    // Dummy node to help build the copied list
    Node copiedListDummyHead = new Node(-1);
    
    // Pointers to traverse original and copied lists
    Node originalCurrent = originalHead;
    Node copiedCurrent = null;
    Node previousCopiedNode = copiedListDummyHead;

    // HashMap to store mapping from original nodes to copied nodes
    Map<Node, Node> originalToCopiedMap = new HashMap<>();

    // Step 1: Copy all nodes (only value and next pointer for now)
    while (originalCurrent != null) {
        Node copiedNode = new Node(originalCurrent.val);
        
        // Link the newly created node
        previousCopiedNode.next = copiedNode;
        
        // Save the mapping
        originalToCopiedMap.put(originalCurrent, copiedNode);
        
        // Move both pointers forward
        previousCopiedNode = copiedNode;
        originalCurrent = originalCurrent.next;
    }

    // Reset pointers to beginning
    originalCurrent = originalHead;
    copiedCurrent = copiedListDummyHead.next;

    // Step 2: Set the random pointers for copied nodes
    while (originalCurrent != null) {
        if (originalCurrent.random != null) {
            copiedCurrent.random = originalToCopiedMap.get(originalCurrent.random);
        }
        // Move both pointers forward
        originalCurrent = originalCurrent.next;
        copiedCurrent = copiedCurrent.next;
    }

    // Return the actual head of the copied list
    return copiedListDummyHead.next;
}