> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/medium/138.-copy-list-with-random-pointer.md).

# 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

```java
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;
}

```