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 random to the node at a random index or null. Construct a deep copy of the given linked list. The linked list is represented in the following way:

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

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

The problem requires creating a deep copy of a linked list with random pointers. A naive approach of iterating and copying would fail because the random pointers could point to arbitrary nodes in the original list. We need a way to track the mappings between original nodes and their copies. Here's a step-by-step approach using a hash map:

1. Create a mapping: Iterate through the original list and create a mapping between each original node and its copy using a hash map (dictionary in Python).

2. Connect next pointers: Iterate again and connect the next pointers of the copied nodes based on the next pointers of the original nodes. Use the hash map to find the copied node corresponding to the next pointer.

3. Connect random pointers: Iterate a third time and connect the random pointers of the copied nodes. Similar to the next pointers, use the hash map to find the correct copied node for the random pointer.

4. Return the head of the copied list: Return the copied node corresponding to the original head node.

Explanation

The hash map is crucial. It allows us to efficiently look up the copied node for each original node, avoiding the need to search through the list repeatedly. This significantly improves the time complexity. The algorithm avoids the complications of recursively creating nodes by creating all copies upfront and then linking them correctly.

Code

class Node:
    def __init__(self, x, next=None, random=None):
        self.val = x
        self.next = next
        self.random = random

def copyRandomList(head: 'Node') -> 'Node':
    if not head:
        return None

    old_to_new = {}  # Hash map to store mappings between original and copied nodes

    # Create copies and populate the map
    curr = head
    while curr:
        old_to_new[curr] = Node(curr.val)
        curr = curr.next

    # Connect next pointers
    curr = head
    while curr:
        old_to_new[curr].next = old_to_new.get(curr.next)  #Handle None next pointer
        curr = curr.next

    # Connect random pointers
    curr = head
    while curr:
        old_to_new[curr].random = old_to_new.get(curr.random)  #Handle None random pointer
        curr = curr.next

    return old_to_new[head]

Complexity

• Time Complexity: O(N), where N is the number of nodes in the list. We iterate through the list three times.
• Space Complexity: O(N), due to the hash map that stores the mappings between original and copied nodes. The space used for the copied list itself is also O(N).