Copy List with Random Pointer

Problem

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

Return the head of the copied linked list.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints:

0 <= n <= 1000
-10^4 <= Node.val <= 10^4
Node.random is null or is pointing to some node in the linked list.

Solution

Approach 1: Hash Map (Two Pass)

The key insight is to use a hash map to store the mapping from original nodes to copied nodes. First pass creates all nodes, second pass sets up pointers.

Implementation

"""
# Definition for a Node.
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: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        # Map original node -> copied node
        old_to_new = {}

        # First pass: create all nodes
        curr = head
        while curr:
            old_to_new[curr] = Node(curr.val)
            curr = curr.next

        # Second pass: set up next and random pointers
        curr = head
        while curr:
            if curr.next:
                old_to_new[curr].next = old_to_new[curr.next]
            if curr.random:
                old_to_new[curr].random = old_to_new[curr.random]
            curr = curr.next

        return old_to_new[head]

Approach 2: Interweaving Nodes (O(1) Space)

We can achieve O(1) space by interweaving copied nodes with original nodes, then separating them.

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        # Step 1: Create copied nodes and interweave them
        curr = head
        while curr:
            copy = Node(curr.val, curr.next)
            curr.next = copy
            curr = copy.next

        # Step 2: Set up random pointers for copied nodes
        curr = head
        while curr:
            if curr.random:
                curr.next.random = curr.random.next
            curr = curr.next.next

        # Step 3: Separate the two lists
        dummy = Node(0)
        copy_curr = dummy
        curr = head
        while curr:
            copy_curr.next = curr.next
            curr.next = curr.next.next
            copy_curr = copy_curr.next
            curr = curr.next

        return dummy.next

Complexity Analysis

Hash Map Approach:

Time Complexity: O(n), where n is the number of nodes. Two passes through the list.
Space Complexity: O(n) for the hash map storing n node mappings.

Interweaving Approach:

Time Complexity: O(n), three passes through the list.
Space Complexity: O(1), not counting the output list. We don’t use extra data structures.

Key Insights

Mapping Challenge: The main challenge is maintaining the relationship between original and copied nodes so we can correctly set up random pointers.
Two-Pass Strategy: Creating all nodes first, then setting pointers second, allows us to guarantee all target nodes exist when we set up random pointers.
Hash Map Trade-off: Using a hash map is intuitive and straightforward but requires O(n) extra space.
Interweaving Trick: By placing copied nodes immediately after their originals (A->A’->B->B’), we can access the copy of any node’s random target via random.next.
None Handling: We must check if next and random pointers are None before trying to access them in the hash map.