Clone List with Next and Random

You are given a special linked list with n nodes where each node has two pointers a next pointer that points to the next node of the singly linked list, and a random pointer that points to the random node of the linked list.

Construct a copy of this linked list. The copy should consist of the same number of new nodes, where each new node has the value corresponding to its original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list, such that it also represent the same list state. None of the pointers in the new list should point to nodes in the original list.

Return the head of the copied linked list.

NOTE : Original linked list should remain unchanged.

Examples:

Input: head = [[1, 3], [3, 3], [5, NULL], [9, 3]] 
      
Output: head = [[1, 3], [3, 3], [5, NULL], [9, 3]] 
Explanation: 
Node 1 points to Node 2 as its NEXT and Node 3 as its RANDOM.
Node 2 points to Node 3 as its NEXT and Node 3 as its RANDOM.
Node 3 points to Node 4 as its NEXT and NULL as its RANDOM.
Node 4 points to NULL as its NEXT and Node 3 as its RANDOM.

Input: head = [[1, 3], [2, 1], [3, 5], [4, 3], [5, 2]]
  
 
Output: head = [[1, 3], [2, 1], [3, 5], [4, 3], [5, 2]]
Explanation: 
Node 1 points to Node 2 as its NEXT and Node 3 as its RANDOM.
Node 2 points to Node 3 as its NEXT and Node 1 as its RANDOM.
Node 3 points to Node 4 as its NEXT and Node 5 as its RANDOM.
Node 4 points to Node 5 as its NEXT and Node 3 as its RANDOM.
Node 5 points to NULL as its NEXT and Node 2 as its RANDOM.

Input: head = [[7, NULL], [7, NULL]]
Output: head = [[7, NULL], [7, NULL]]
Explanation: 
Node 1 points to Node 2 as its NEXT and NULL as its RANDOM.
Node 2 points to NULL as its NEXT and NULL as its RANDOM.

Constraints:
1 <= n <= 100
0 <= node->data <= 1000

Approach 01:

class Solution {
public:
    Node* copyList(Node* head) {
        // Map to store the original node to its copy
        unordered_map<Node*, Node*> nodeMap;
        Node* currentNode = head;
        
        // First pass: Create new nodes and store them in the map
        while (currentNode) {
            nodeMap[currentNode] = new Node(currentNode->data);
            currentNode = currentNode->next;
        }
        
        currentNode = head;
        
        // Second pass: Assign next and random pointers for the copied nodes
        while (currentNode) {
            nodeMap[currentNode]->next = currentNode->next ? nodeMap[currentNode->next] : nullptr;
            nodeMap[currentNode]->random = currentNode->random ? nodeMap[currentNode->random] : nullptr;
            currentNode = currentNode->next;
        }
        
        // Return the head of the copied list
        return nodeMap[head];
    }
};

class Solution:
    def cloneLinkedList(self, head):
        if head is None:
            return None

        # Step 1: Create copies of each node and link them in between original nodes
        currentNode = head
        while currentNode:
            clonedNode = Node(currentNode.data)
            clonedNode.next = currentNode.next
            currentNode.next = clonedNode
            currentNode = clonedNode.next

        # Step 2: Set the random pointers for the cloned nodes
        currentNode = head
        while currentNode:
            if currentNode.random:
                currentNode.next.random = currentNode.random.next
            currentNode = currentNode.next.next

        # Step 3: Separate the original and cloned linked lists
        originalNode = head
        clonedHead = head.next
        clonedNode = clonedHead

        while originalNode:
            originalNode.next = originalNode.next.next
            if clonedNode.next:
                clonedNode.next = clonedNode.next.next
            originalNode = originalNode.next
            clonedNode = clonedNode.next

        return clonedHead

Time Complexity:

• First Pass:

  Creating new nodes and storing them in the map involves iterating through the original linked list, taking \( O(n) \), where \( n \) is the number of nodes in the list.

• Second Pass:

  Assigning the next and random pointers for the copied nodes also takes \( O(n) \), as we iterate through the list again.

• Overall Time Complexity:

  The total time complexity is \( O(n) \).

Space Complexity:

• Hash Map:

  The hash map stores one entry for each node in the original list, requiring \( O(n) \) space.

• Copied List:

  The copied linked list requires \( O(n) \) space to store the new nodes.

• Overall Space Complexity:

  The total space complexity is \( O(n) \).