Copy List with Random Pointer medium

Problem Statement

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list. The deep copy should consist of new nodes and new random pointers. The original list should not be changed.

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

Explanation:

Node 0's val is 7, and both its next and random pointer point to node 1. Node 1's val is 13, its next pointer points to node 2, and its random pointer points to node 0. Node 2's val is 11, its next pointer points to node 3, and its random pointer points to node 4. Node 3's val is 10, its next pointer points to node 4, and its random pointer points to node 2. Node 4's val is 1, its next pointer is null, and its random pointer points to node 0.

Example 2

Input: head = [] Output: []

Steps

1. Create a map: Create a Map to store the mapping between original nodes and their corresponding copied nodes. This will allow us to easily access copied nodes later.

2. First pass: Copy nodes and their next pointers: Iterate through the original list. For each node, create a new node with the same val and add it to the map. Connect the next pointers of the copied nodes, mimicking the original list's structure.

3. Second pass: Copy random pointers: Iterate through the original list again. For each node, retrieve its copied node from the map. Then, look up the random pointer of the original node; find its copy using the map, and set the copied node's random pointer to the copied random pointer.

4. Return the head of the copied list: Return the first copied node.

Explanation

The solution employs a two-pass approach to avoid needing to iterate the list more than twice. The map acts as a crucial intermediary that links original and copied nodes ensuring we can correctly set both next and random pointers efficiently. The first pass ensures that the basic linked list structure is copied. The second pass handles the more complex random pointer connections.

Code

class Node {
    val: number;
    next: Node | null;
    random: Node | null;

    constructor(val?: number, next?: Node, random?: Node) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
        this.random = random === undefined ? null : random;
    }
}

function copyRandomList(head: Node | null): Node | null {
    if (!head) return null;

    const map = new Map<Node, Node>(); // Map original nodes to copied nodes

    // First pass: Copy nodes and next pointers
    let current = head;
    let copiedHead = new Node(head.val); // Create the first copied node
    map.set(head, copiedHead);
    let copiedCurrent = copiedHead;

    while (current.next) {
        const nextCopiedNode = new Node(current.next.val);
        copiedCurrent.next = nextCopiedNode;
        map.set(current.next, nextCopiedNode);
        current = current.next;
        copiedCurrent = copiedCurrent.next;
    }

    // Second pass: Copy random pointers
    current = head;
    copiedCurrent = copiedHead;
    while (current) {
        if (current.random) {
            copiedCurrent.random = map.get(current.random)!;
        }
        current = current.next;
        copiedCurrent = copiedCurrent.next;
    }

    return copiedHead;
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. We iterate through the list twice.
• Space Complexity: O(N), due to the use of the Map to store the node mappings. In the worst case, all nodes need to be stored in the map.