Copy List with Random Pointer

PracticeNeetCode ↗LeetCode ↗

Each node in this linked list carries an extra random pointer that can point to any node in the list, or to None. Return a deep copy of the list — a fully independent structure with the same values and the same relative next/random wiring.

Example

Key Pointers

• A hashmap from original node → copied node lets you resolve random pointers even before the whole list is built.
• Split it into two passes: first create every copied node (values only), then a second pass to wire both next and random using the map.
• Mapping None → None up front avoids special-casing random pointers that point to nothing.

Step-by-Step Analysis

1. First pass: walk the original list, creating a copy of each node and recording old_node → copy in a hashmap.
2. Second pass: walk the original list again; for each node set copy.next = mapping[node.next] and copy.random = mapping[node.random].
3. Return mapping[head] as the head of the copied list.

Complexity

Time: O(n) — Space: O(n)

Code

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

def copyRandomList(head: "Node | None") -> "Node | None":
    if not head:
        return None

    mapping = {None: None}
    curr = head
    while curr:
        mapping[curr] = Node(curr.val)
        curr = curr.next

    curr = head
    while curr:
        mapping[curr].next = mapping[curr.next]
        mapping[curr].random = mapping[curr.random]
        curr = curr.next

    return mapping[head]

Code Explanation

How the solution above works, piece by piece.

1. mapping = {None: None}: old node → new node. The None entry means a missing next or random maps to None automatically.
2. Pass 1: walk the list and create a bare copy of each node (value only).
3. Pass 2: for each original node, mapping[curr].next = mapping[curr.next] and mapping[curr].random = mapping[curr.random].
4. Two passes are needed because a random pointer can point forward to a node whose copy wouldn't exist yet in a single pass.
5. Return mapping[head]. O(n) time, O(n) space for the map.

Visual Walkthrough

Running it on the example (random targets: 7 → None, 13 → 7, 11 → 1, 10 → 11, 1 → 7):

Video Explanation

NeetCode — Copy List with Random Pointer, LeetCode 138