algoadvance

Problem Summary:

A linked list is given where each node contains an additional random pointer, which could point to any node in the list or to null. The task is to create a deep copy of this list.

Each node is defined as:

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

Clarifying Questions

  1. Q: Are the values of the nodes guaranteed to be unique? A: No, node values are not necessarily unique, but the random pointers can point to any node or null.

  2. Q: Do we need to handle any special edge cases like an empty list? A: Yes, we need to handle the case where the input list is empty.

Strategy

The strategy to solve this problem involves three main steps:

  1. Step 1: Copying the Nodes and Creating a Mapping
    • Iterate through the original list and create a copy of each node.
    • Store the mapping of old nodes to new nodes using a hash map (dictionary).
  2. Step 2: Setting Next and Random Pointers
    • Iterate through the original list again to update the next and random pointers of the copied nodes using the previously created mapping.
  3. Step 3: Extract and Return the Deep Copy
    • Return the head of the new list.

Implementation

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

def copyRandomList(head: 'Node') -> 'Node':
    if not head:
        return None
    
    # Creating a mapping from old nodes to new nodes
    old_to_new = {}

    # Step 1: Create a copy of each node and store it in the dictionary
    current = head
    while current:
        old_to_new[current] = Node(current.val)
        current = current.next

    # Step 2: Assign the next and random pointers
    current = head
    while current:
        if current.next:
            old_to_new[current].next = old_to_new[current.next]
        if current.random:
            old_to_new[current].random = old_to_new[current.random]
        current = current.next

    # Step 3: Return the head of the new list
    return old_to_new[head]

Time Complexity

This completes our implementation and explanation. If there are additional questions or edge cases to consider, feel free to ask!

Try our interview co-pilot at AlgoAdvance.com