# Copy List with Random Pointer

> How to solve Copy List with Random Pointer: deep clone a list with random pointers using a hash map from old nodes to new nodes.

- Difficulty: Medium
- Category: Linked List
- Topics: Linked List, Hash Table
- Published 2026-08-21

## Problem

You are given the head of a linked list where every node has an ordinary `next` pointer plus an extra `random` pointer that can point to any other node, or to nothing. Produce a completely independent deep copy: new nodes with the same values, whose `next` and `random` pointers mirror the original structure but never point back into it.

**Example.** A three-node list `A -> B -> C` where `A.random` points to `C` must be copied into a fresh `A' -> B' -> C'` where `A'.random` points to `C'`, not to the original `C`.

## Key idea

The difficulty is that a node's `random` pointer can target a node anywhere in the list, including one not yet created when the copy is built in list order. A naive single pass that sets `random` immediately runs into targets that do not exist yet.

The fix uses a hash map from each original node to its freshly created copy. In a first pass, walk the original list and create one bare copy node per original, recording the mapping as each is made. In a second pass, walk again and use the map to wire up each copy's `next` and `random`: a copy's `next` is the mapped copy of the original's `next`, and likewise for `random`. Because every node was already mapped in the first pass, every lookup in the second succeeds.

## Solution

```typescript
class Node {
  val: number;
  next: Node | null;
  random: Node | null;
  constructor(val = 0, next: Node | null = null, random: Node | null = null) {
    this.val = val;
    this.next = next;
    this.random = random;
  }
}

function copyRandomList(head: Node | null): Node | null {
  if (head === null) {
    return null;
  }

  const oldToNew = new Map<Node, Node>(); // maps each original node to its copy

  let curr: Node | null = head;
  while (curr !== null) {
    oldToNew.set(curr, new Node(curr.val)); // first pass: create bare copies, no links yet
    curr = curr.next;
  }

  curr = head;
  while (curr !== null) {
    const copy = oldToNew.get(curr)!;
    copy.next = curr.next !== null ? oldToNew.get(curr.next)! : null; // second pass: every node is already mapped, so lookups always succeed
    copy.random = curr.random !== null ? oldToNew.get(curr.random)! : null;
    curr = curr.next;
  }

  return oldToNew.get(head)!;
}
```

## Complexity

- **Time:** O(n). Two linear passes over the list.
- **Space:** O(n). The hash map holds one entry per node, in addition to the output copy itself.

## Watch out for

- A `random` pointer that is null must map to null in the copy, not be treated as a missing lookup.
- The map must be keyed by node identity, not by value, since values can repeat.
- Build every copy node before wiring any pointers: wiring during the first pass risks pointing at a copy not yet created.

## Pattern

This is the "clone via mapping" pattern: build an old-to-new correspondence first, then rewire all pointers using that lookup. The same idea drives deep-copying any graph-like structure, including Clone Graph.

---

Canonical URL: https://www.marauderbot.com/questions/copy-list-with-random-pointer
