deepSWE.io

Copy List with Random Pointer

Linked ListHash Map

25-30 min

Problem Statement

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.

Example

Example 1:

Constraints

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

Solutions

Approach 1: Hash Map

This approach uses a hash map to store a mapping from each original node to its corresponding new copy. This allows us to easily set the `next` and `random` pointers in a second pass.

Hash Map Visualization

Step 0: Initial State

Algorithm Steps

Traverse the original list and create a copy of each node. Store the mapping from old node to new node in a hash map.
Traverse the original list again. For each node, use the hash map to set the `next` and `random` pointers of its copy.
Return the head of the copied list from the hash map.

Hash Map Solution


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

        # First pass: create copies of all nodes
        curr = head
        while curr:
            old_to_copy[curr] = Node(curr.val)
            curr = curr.next
            
        # Second pass: set the next and random pointers
        curr = head
        while curr:
            copy = old_to_copy[curr]
            copy.next = old_to_copy.get(curr.next)
            copy.random = old_to_copy.get(curr.random)
            curr = curr.next
            
        return old_to_copy[head]

Approach 2: Interweaving Nodes

This optimal approach avoids using extra space for a hash map by cleverly interweaving the original and copied nodes.

Interweaving Visualization

Step 0: Initial State

Algorithm Steps

Step 1: Create a copy of each node and place it immediately after the original node in the list.
Step 2: Traverse the interwoven list. For each original node, set the `random` pointer of its copy.
Step 3: Separate the interwoven list into the original list and the copied list.

Interweaving Nodes Solution


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

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

        # Step 2: Assign random pointers
        ptr = head
        while ptr:
            if ptr.random:
                ptr.next.random = ptr.random.next
            ptr = ptr.next.next

        # Step 3: Separate the lists
        old_head = head
        new_head = head.next
        ptr_old = old_head
        ptr_new = new_head
        while ptr_old:
            ptr_old.next = ptr_old.next.next
            ptr_new.next = ptr_new.next.next if ptr_new.next else None
            ptr_old = ptr_old.next
            ptr_new = ptr_new.next
            
        return new_head