Deep Copy of a Linked List with Random Pointers

Problem Description

Given a linked list where each node has a next pointer and a random pointer (which can point to any node or be null), create a deep copy of the list.

Naive Approach (Brute Force)

1. Create New Nodes: Iterate through the original list and create a new node for each original node, storing the value of the original node in the new node.
2. Store Mapping: Use a hash map (dictionary) to store the mapping between original nodes and their corresponding new nodes.
3. Set next Pointers: Iterate through the original list again. For each node, find its corresponding new node in the hash map, and set the next pointer of the new node to the new node corresponding to the original node's next pointer (if it exists).
4. Set random Pointers: Iterate through the original list one more time. For each node, find its corresponding new node in the hash map, and set the random pointer of the new node to the new node corresponding to the original node's random pointer (if it exists).
5. Return Head: Return the head of the new list.

Code (Python)

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


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

    # 1. Create new nodes and store the mapping
    old_to_new = {}
    curr = head
    while curr:
        new_node = Node(curr.val)
        old_to_new[curr] = new_node
        curr = curr.next

    # 2. Set next pointers
    curr = head
    while curr:
        new_node = old_to_new[curr]
        if curr.next:
            new_node.next = old_to_new[curr.next]
        curr = curr.next

    # 3. Set random pointers
    curr = head
    while curr:
        new_node = old_to_new[curr]
        if curr.random:
            new_node.random = old_to_new[curr.random]
        curr = curr.next

    return old_to_new[head]

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the linked list. We iterate through the list three times.
• Space Complexity: O(n), because we use a hash map to store the mapping between original nodes and new nodes.

Optimal Approach

The optimal solution reduces the space complexity to O(1) by weaving the new nodes into the original list. After creating the new nodes, interweave the original and copied list, and then adjust the random pointers.

1. Interweave New Nodes: Iterate through the original list and create a new node after each original node. E.g., A -> B -> C becomes A -> A' -> B -> B' -> C -> C'.
2. Set random Pointers: Iterate through the interweaved list. For each new node, its random pointer should point to the copy of the node its original counterpart's random pointer points to. E.g., A'.random = A.random.next (if A.random exists).
3. Separate Lists: Separate the original list and the copied list. This involves updating the next pointers of both lists to restore the original list and form the new copied list.

Code (Python)

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

    # 1. Interweave new nodes
    curr = head
    while curr:
        new_node = Node(curr.val)
        new_node.next = curr.next
        curr.next = new_node
        curr = new_node.next

    # 2. Set random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next

    # 3. Separate lists
    curr = head
    new_head = head.next
    new_curr = new_head

    while curr:
        curr.next = new_curr.next
        curr = curr.next
        if curr:
            new_curr.next = curr.next
            new_curr = new_curr.next
        else:
            new_curr.next = None

    return new_head

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the linked list. We iterate through the list three times.
• Space Complexity: O(1), because we do not use any extra space other than a few pointers. The new nodes are created in place.

Edge Cases

• Empty List: If the input list is empty (head is None), return None.
• Single Node List: The algorithm should work correctly for a list with only one node.
• random Pointer is None: The algorithm should handle cases where the random pointer of a node is None.