138. Copy List with Random Pointer

This problem involves creating a deep copy of a linked list where each node has a next pointer and a random pointer that can point to any node in the list (or null). The deep copy must be entirely new nodes, not referencing any nodes from the original list.

Approach 1: Hash Table

This approach uses a hash table (dictionary in Python) to store mappings between original nodes and their corresponding new nodes.

1. Create Copies and Map: Iterate through the original list. For each node, create a new node with the same value. Store the mapping between the original node and the new node in the hash table. Simultaneously, link the next pointers of the new nodes to create a correctly ordered list.

2. Connect Random Pointers: Iterate through the original list again. For each node, use the hash table to find the corresponding new node and set its random pointer based on the original node's random pointer. If the original random pointer is null, the new node's random pointer is also null.

Time Complexity: O(N), where N is the number of nodes in the list. We iterate through the list twice.

Space Complexity: O(N). The hash table stores N mappings.

Code (Python):

class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
 
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
 
        node_map = {}  # Hash table to store mappings
 
        curr = head
        dummy = tail = Node(0) # Dummy node for easy list creation
 
        while curr:
            new_node = Node(curr.val)
            node_map[curr] = new_node  # Store the mapping
            tail.next = new_node
            tail = new_node
            curr = curr.next
 
        curr = head
        tail = dummy.next #start from the first copied node
        while curr:
            new_node = node_map[curr]
            new_node.random = node_map.get(curr.random) #Get the random pointer from the map, or None if it's null
            curr = curr.next
            tail = tail.next
        return dummy.next
 

Approach 2: In-place Copying (Space Optimization)

This approach avoids the extra space of a hash table by cleverly inserting new nodes in-place.

1. Interleave Nodes: Iterate through the list. For each node, create a new node and insert it immediately after the original node. Connect the next pointers appropriately.

2. Connect Random Pointers: Iterate through the modified list. The new nodes are now interleaved with the original ones. Set the random pointer of each new node based on the original node's random pointer (considering the interleaving).

3. Separate Lists: Iterate through the list again to separate the original and copied lists.

Time Complexity: O(N). We iterate through the list three times.

Space Complexity: O(1). We only use a constant amount of extra space.

Code (Python):

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
 
        # Interleave new nodes
        curr = head
        while curr:
            new_node = Node(curr.val)
            new_node.next = curr.next
            curr.next = new_node
            curr = new_node.next
 
        # Connect random pointers
        curr = head
        while curr:
            if curr.random:
                curr.next.random = curr.random.next
            curr = curr.next.next
 
        # Separate lists
        curr = head
        copy_head = head.next
        while curr:
            new_node = curr.next
            curr.next = new_node.next
            if new_node.next:
                new_node.next = new_node.next.next
            curr = curr.next
        return copy_head
 

Both approaches correctly solve the problem. The hash table approach is easier to understand, while the in-place approach is more space-efficient. Choose the approach that best suits your needs and understanding. The code examples provided are in Python, but the concepts can be easily adapted to other programming languages.