Technical Interview Question

You are given a linked list where each node has a next pointer and a random pointer. The next pointer points to the next node in the list, and the random pointer could point to any node in the list or null. You need to write a function that makes a deep copy of the original linked list with the random pointers also copied correctly.

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

def copyRandomList(head: 'Node') -> 'Node':
    # Your solution

Answer

To make a deep copy of the given linked list, we will use a mapping to associate original nodes to their clones. We will iterate through the original list, creating new nodes and mapping the original node to its clone. Then we will iterate through the list again to update the next and random pointers in the cloned list.

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

    ptr = head
    clone_map = {}

    # First pass: Create a clone for each node and build a map of original node to its clone
    while ptr:
        clone_map[ptr] = Node(ptr.val)
        ptr = ptr.next

    ptr = head

    # Second pass: Assign the next and random pointers of the cloned nodes
    while ptr:
        clone_map[ptr].next = clone_map.get(ptr.next)
        clone_map[ptr].random = clone_map.get(ptr.random)
        ptr = ptr.next

    return clone_map[head]

This solution has a time complexity of O(n) where n is the number of nodes in the linked list, and a space complexity of O(n) due to the mapping used to store original nodes and their clones.