Copy List with Random Pointer medium

Problem Statement

A linked list of length n is given such that each node contains an integer val and a pointer to the next node in the list. The integer val can be 0 or 1. You are given the head of the linked list and the nodes are in the range [0, n - 1]. You need to construct a deep copy of this linked list and return the head of the copied list. Each node in the deep copy should have the same val, next, and random pointers as the corresponding node in the original list. Note: the random pointers in the copied list do not necessarily point to the correct nodes. The random pointer in the original list could be pointing to null, or to any node in the original list.

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

Steps

1. Create a map: Use a HashMap to store the mapping between the original nodes and their corresponding copied nodes. This will help us avoid redundant node creation and ensure correct random pointer connections.

2. Iterate and copy: Traverse the original linked list. For each node, create a new node with the same val. Put the mapping of the original node and the copied node into the HashMap.

3. Connect next pointers: While iterating, connect the next pointer of the copied node to the copied version of the original node's next node (obtained from the HashMap).

4. Connect random pointers: After creating all nodes and connecting next pointers, iterate again to connect the random pointers. Use the HashMap to find the copied version of the original node pointed to by the random pointer.

5. Return the head: Return the head of the copied linked list.

Explanation

The solution uses a HashMap to efficiently track the mapping between original and copied nodes. This avoids the need for repetitive searches during the process of linking next and random pointers. The two iterations ensure that all nodes are created before attempting to connect their random pointers. This strategy is crucial for correctness. If we tried to connect random pointers during the first iteration, the copied nodes referenced by those pointers might not yet exist in the HashMap.

Code

import java.util.HashMap;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

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

        HashMap<Node, Node> map = new HashMap<>();
        Node newHead = new Node(head.val); // Create head for copied list
        map.put(head, newHead);


        Node currOriginal = head;
        Node currCopy = newHead;

        // Iterate and create copies, link next pointers
        while (currOriginal != null) {
            if (currOriginal.next != null) {
                if (!map.containsKey(currOriginal.next)) {
                    map.put(currOriginal.next, new Node(currOriginal.next.val));
                }
                currCopy.next = map.get(currOriginal.next);
            }
            currOriginal = currOriginal.next;
            currCopy = currCopy.next;
        }


        currOriginal = head;
        currCopy = newHead;

        //Iterate again and link random pointers
        while (currOriginal != null){
            if(currOriginal.random != null){
                currCopy.random = map.get(currOriginal.random);
            }
            currOriginal = currOriginal.next;
            currCopy = currCopy.next;
        }

        return newHead;
    }


    public static void main(String[] args) {
        //Example Usage (You can adapt this to test other inputs)
        Node head = new Node(7);
        head.next = new Node(13);
        head.next.next = new Node(11);
        head.next.next.next = new Node(10);
        head.next.next.next.next = new Node(1);
        head.random = null;
        head.next.random = head;
        head.next.next.random = head.next.next.next.next;
        head.next.next.next.random = head.next;
        head.next.next.next.next.random = head;

        CopyListWithRandomPointer solution = new CopyListWithRandomPointer();
        Node copiedHead = solution.copyRandomList(head);


        // Print copied list (For verification purposes)
        Node curr = copiedHead;
        while(curr != null){
            System.out.print("[" + curr.val);
            if(curr.random != null) System.out.print("," + curr.random.val);
            else System.out.print(",null");
            System.out.print("]");
            if(curr.next != null) System.out.print("->");
            curr = curr.next;
        }
    }
}

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). The HashMap stores at most N entries (one for each node).