Problem 23 · Linked Lists

Copy List with Random Pointer

MediumClassic DSA & systems

01Problem

Each node has a next pointer and a random pointer to any node or null. Return a deep copy of the list.

02Key insight

Map each original node to its clone (hash map) in one pass, then wire next/random in a second pass; the O(1)-space variant interleaves clones between originals.

03Solution

solution.pypython19 lines

from __future__ import annotations
from typing import Optional

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

def copy_random_list(head: Optional[Node]) -> Optional[Node]:
    clones: dict[Node, Node] = {}
    node = head
    while node:
        clones[node] = Node(node.val)
        node = node.next
    node = head
    while node:
        clones[node].next = clones.get(node.next)
        clones[node].random = clones.get(node.random)
        node = node.next
    return clones.get(head)

Try it first.

TimeO(n)

SpaceO(n)

tests.py · 4 passing

tests.pypython8 lines

a, b, c = Node(1), Node(2), Node(3)
a.next, b.next = b, c
a.random, b.random, c.random = c, a, None
copy = copy_random_list(a)
assert copy is not a and copy.val == 1 and copy.next.val == 2
assert copy.random is copy.next.next and copy.next.random is copy
assert copy.next.next.random is None and copy.random is not c
assert copy_random_list(None) is None

04Staff-level follow-up

Memory-constrained? Interleave A->A'->B->B', set A'.random = A.random.next, then unweave: O(1) extra space but mutates the input temporarily, which is unsafe under concurrent readers.