LeetCode Solutions Blog

Copy List with Random Pointer

Number: 138

Difficulty: Medium

Paid? No

Problem Description

Given the head of a linked list where each node contains an extra pointer, random, that can point to any node in the list or null, create a deep copy of the list. The new list must have exactly n brand new nodes where both the next and random pointers replicate the original list’s structure without pointing to nodes in the original list.

Key Insights

Use a hash map (or dictionary) to map each original node to its corresponding copy.
Perform two passes: the first to create a copy of each node, and the second to assign the next and random pointers using the hash map.
An alternative interleaving approach exists but using a hash table is typically more straightforward.

Space and Time Complexity

Time Complexity: O(n) – Each node is processed a constant number of times. Space Complexity: O(n) – A hash map is used to store the mapping from original nodes to their copies.

Solution

The solution uses a two-pass algorithm. In the first pass, we iterate through the original list and for each node, create a new node (deep copy) while saving the mapping between the original and copy in a hash table. In the second pass, we iterate over the original list again to assign the next and random pointers of the new nodes using the previously built map. This guarantees that every pointer in the copied list corresponds to a new node and not the original.

Code Solutions

# Definition for a Node.
class Node:
    def __init__(self, val, next=None, random=None):
        self.val = val       # value of the node.
        self.next = next     # pointer to the next node.
        self.random = random # pointer to a random node.

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        # Return None if the head is None.
        if not head:
            return None

        # Dictionary to hold old node as key and new node as value.
        old_to_new = {}

        # First pass: create a copy of each node.
        current = head
        while current:
            old_to_new[current] = Node(current.val)
            current = current.next

        # Second pass: assign next and random pointers for the copied nodes.
        current = head
        while current:
            # Using dict.get ensures proper assignment or returns None.
            old_to_new[current].next = old_to_new.get(current.next)
            old_to_new[current].random = old_to_new.get(current.random)
            current = current.next

        # Return the head of the new copied linked list.
        return old_to_new[head]