138. Copy List with Random Pointer

#linked-list

Problem

Copy List with Random Pointer - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

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

class Solution {
    public Node copyRandomList(Node head) {
        // n -> number of nodes in linked list
        // Time Complexity: O(n)
        // O(n) [building map] + O(n) [building new linked list] = 2 * O(n) = O(n)
        
        // Space Complexity: O(n), to store values in hashmap
         
        // Check if the original list is empty
        if (head == null) {
            return null;
        }

        // Create a mapping between original nodes and their corresponding copies
        Map<Node, Node> map = new HashMap<>();

        // First pass: Create copies of all nodes without connections
        Node node = head;
        while (node != null) {
            // Create a new copy node with the same value as the original node
            map.put(node, new Node(node.val));
            node = node.next;
        }

        // Second pass: Assign next and random pointers for the copied nodes
        node = head;
        while (node != null) {
            // Get the copy node corresponding to the original node
            Node copyNode = map.get(node);

            // Assign the next pointer of the copy node using the mapping
            copyNode.next = map.get(node.next);

            // Assign the random pointer of the copy node using the mapping
            copyNode.random = map.get(node.random);

            // Move to the next original node
            node = node.next;
        }

        // Return the head of the copied list
        return map.get(head);
    }
}