Problem Description

You are given a linked list where each node has two pointers:

• A next pointer that points to the next node in the list (or null if it's the last node)
• A random pointer that can point to any node in the list (or null)

Your task is to create a deep copy of this linked list. A deep copy means:

• Create n brand new nodes (where n is the length of the original list)
• Each new node should have the same value as its corresponding original node
• The next and random pointers in the copied list should maintain the same structure as the original list, but must point to the new copied nodes, not the original ones

For example, if in the original list node X has X.random pointing to node Y, then in the copied list, the corresponding node x should have x.random pointing to the corresponding copied node y.

The solution uses a hash table approach:

1. First pass: Traverse the original list, create a copy of each node, and store the mapping between original nodes and their copies in a hash table d. During this pass, also connect the next pointers of the copied nodes.
2. Second pass: Traverse the original list again and use the hash table to set up the random pointers for the copied nodes. For each original node, find its copy in the hash table, then set the copy's random pointer to point to the copy of the original node's random target.

The function returns the head of the newly created deep copy of the linked list.

Intuition

The main challenge in this problem is handling the random pointers. When we're creating a copy of a node, its random pointer might reference a node that we haven't created yet, or it might reference a node we've already passed.

Consider what happens if we try to copy the list in a single pass: When we copy node A, and A's random pointer points to node C (which comes later in the list), we can't set up this connection yet because node C's copy doesn't exist. Similarly, if A's random pointer points backwards to a previously copied node, we need a way to find that copied node.

This naturally leads us to think about maintaining a mapping between original nodes and their copies. A hash table is perfect for this - it gives us O(1) access to find any copied node given its original.

The solution becomes clear: we need two passes through the list:

1. First pass: Create all the new nodes and establish the mapping. While we're at it, we can connect the next pointers since they follow a sequential pattern.
2. Second pass: Now that all nodes are created and we have our mapping, we can properly set up the random pointers. For each original node, we look up its copy, then set the copy's random pointer to point to the copy of wherever the original's random points.

The key insight is that we must separate node creation from random pointer assignment. The hash table serves as the bridge between the original and copied lists, allowing us to translate any reference from the original list to its corresponding reference in the copied list.

Solution Approach

The implementation uses a hash table to maintain the mapping between original nodes and their copies. Here's the step-by-step walkthrough:

Initialization:

• Create a dummy head node dummy to simplify list construction
• Use a tail pointer initialized to dummy to track where to append new nodes
• Initialize an empty dictionary d to store the mapping between original and copied nodes
• Set cur pointer to the original list's head

First Pass - Node Creation and Next Pointer Setup:

while cur:
    node = Node(cur.val)      # Create a new node with same value
    tail.next = node           # Connect to the previous copied node
    tail = tail.next           # Move tail to the newly created node
    d[cur] = node             # Store mapping: original -> copy
    cur = cur.next            # Move to next original node

During this pass:

• We traverse the original list once
• For each original node, we create a corresponding new node with the same value
• We build the next pointer chain for the copied list
• We populate the hash table d where keys are original nodes and values are their copies

Second Pass - Random Pointer Setup:

cur = head                    # Reset to start of original list
while cur:
    d[cur].random = d[cur.random] if cur.random else None
    cur = cur.next

During this pass:

• We traverse the original list again
• For each original node, we access its copy via d[cur]
• We set the copy's random pointer by looking up where the original's random points
• If cur.random exists, we use d[cur.random] to get the corresponding copied node
• If cur.random is None, we set the copy's random to None as well

Return the Result:

• Return dummy.next, which is the head of the deep copied list

The time complexity is O(n) where n is the number of nodes (two passes through the list), and the space complexity is O(n) for the hash table storing the node mappings.

Example Walkthrough

Let's walk through a small example with 3 nodes to illustrate the solution approach.

Original List:

Node 1 (val=7) -> Node 2 (val=13) -> Node 3 (val=11) -> null
Random pointers:
- Node 1.random -> null
- Node 2.random -> Node 1
- Node 3.random -> Node 2

Step-by-step execution:

Initialization:

• Create dummy node (helper node for building the copy)
• tail = dummy (points to where we'll append next)
• d = {} (empty hash table)
• cur = head (points to Node 1)

First Pass - Creating nodes and setting next pointers:

Iteration 1: cur points to Node 1 (val=7)

• Create new Node 1' with val=7
• tail.next = Node 1' (dummy -> Node 1')
• tail = Node 1'
• d[Node 1] = Node 1' (store mapping)
• cur = cur.next (move to Node 2)

Iteration 2: cur points to Node 2 (val=13)

• Create new Node 2' with val=13
• tail.next = Node 2' (Node 1' -> Node 2')
• tail = Node 2'
• d[Node 2] = Node 2' (store mapping)
• cur = cur.next (move to Node 3)

Iteration 3: cur points to Node 3 (val=11)

• Create new Node 3' with val=11
• tail.next = Node 3' (Node 2' -> Node 3')
• tail = Node 3'
• d[Node 3] = Node 3' (store mapping)
• cur = cur.next (becomes null, exit loop)

After First Pass:

• Copied list structure: Node 1' -> Node 2' -> Node 3' -> null
• Hash table d:

  {
    Node 1 -> Node 1',
    Node 2 -> Node 2',
    Node 3 -> Node 3'
  }

Second Pass - Setting random pointers:

Iteration 1: cur points to Node 1

• cur.random is null
• Set d[Node 1].random = None (Node 1'.random = null)
• cur = cur.next (move to Node 2)

Iteration 2: cur points to Node 2

• cur.random points to Node 1
• Set d[Node 2].random = d[Node 1] (Node 2'.random = Node 1')
• cur = cur.next (move to Node 3)

Iteration 3: cur points to Node 3

• cur.random points to Node 2
• Set d[Node 3].random = d[Node 2] (Node 3'.random = Node 2')
• cur = cur.next (becomes null, exit loop)

Final Result: The deep copied list has the structure:

Node 1' (val=7) -> Node 2' (val=13) -> Node 3' (val=11) -> null
Random pointers:
- Node 1'.random -> null
- Node 2'.random -> Node 1'
- Node 3'.random -> Node 2'

The function returns dummy.next, which is Node 1', the head of our deep copied list. Notice how all the pointers in the copied list point to copied nodes, not the original ones, achieving a true deep copy.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two sequential while loops:

• The first loop iterates through all n nodes in the original linked list to create new nodes and build the mapping dictionary. Each operation inside this loop (creating a node, updating pointers, adding to dictionary) takes O(1) time.
• The second loop iterates through all n nodes again to set the random pointers using the dictionary lookup, which is O(1) per operation.

Therefore, the total time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses additional space for:

• A dictionary d that stores mappings from original nodes to copied nodes, containing n key-value pairs: O(n)
• The new linked list with n nodes that are being created as the deep copy: O(n)
• A few constant auxiliary variables (dummy, tail, cur, node): O(1)

The space for the output linked list is typically considered part of the space complexity for this problem, so the total space complexity is O(n).

Common Pitfalls

1. Attempting to Set Random Pointers Before Creating All Nodes

A common mistake is trying to set up the random pointers while creating the nodes in a single pass. This fails because a node's random pointer might point to a node that hasn't been created yet.

Incorrect Approach:

def copyRandomList(self, head: Optional['Node']) -> Optional['Node']:
    if not head:
        return None
  
    original_to_copy = {}
    dummy = Node(0)
    tail = dummy
    current = head
  
    while current:
        new_node = Node(current.val)
        tail.next = new_node
        tail = tail.next
        original_to_copy[current] = new_node
      
        # WRONG: Trying to set random pointer immediately
        # This fails if current.random hasn't been copied yet
        if current.random:
            new_node.random = original_to_copy[current.random]  # KeyError!
      
        current = current.next
  
    return dummy.next

Solution: Always use two separate passes - first create all nodes and establish the mapping, then set up the random pointers.

2. Not Handling None Values in the Hash Table Lookup

Another pitfall is forgetting that the random pointer can be None, and trying to look up None in the dictionary will cause a KeyError.

Incorrect Approach:

# Second pass - WRONG
current = head
while current:
    # This fails when cur.random is None
    original_to_copy[current].random = original_to_copy[current.random]
    current = current.next

Solution: Always check if the random pointer is None before attempting the dictionary lookup:

# Correct approach
if current.random:
    original_to_copy[current].random = original_to_copy[current.random]
else:
    original_to_copy[current].random = None

3. Modifying the Original List

Some might try to optimize by temporarily modifying the original list structure (like interweaving copied nodes with original nodes). This violates the requirement of keeping the original list intact.

Incorrect Approach:

# Trying to insert copied nodes between original nodes
current = head
while current:
    copy = Node(current.val)
    copy.next = current.next  # Modifying original structure
    current.next = copy
    current = copy.next

Solution: Use a separate data structure (hash table) to maintain the mapping without modifying the original list.

4. Forgetting to Return the Correct Head

When using a dummy node, forgetting to return dummy.next instead of dummy itself is a common mistake that would include the dummy node in the result.

Solution: Always return dummy.next to skip the dummy node and return the actual head of the copied list.