Q42: Copy List with Random Pointer. - DSA Patterns (Multi-Lang)

In Simple Words: Two passes with a Hash Map mapping oldNode -> newNode.

Pass 1: Clone all nodes without pointers into the map.
Pass 2: Connect map[curr].next = map[curr.next] and map[curr].random = map[curr.random].

Time: $O(N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

class Node:
    def __init__(self, x: int, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random

def copyRandomList(head: Node | None) -> Node | None:
    if not head: return None
    old_to_new = {}
    curr = head
    while curr:
        old_to_new[curr] = Node(curr.val)
        curr = curr.next
    curr = head
    while curr:
        old_to_new[curr].next = old_to_new.get(curr.next)
        old_to_new[curr].random = old_to_new.get(curr.random)
        curr = curr.next
    return old_to_new[head]