Skip to main content

77. Copy List with Random Pointer

mediumAsked at Vercel

Deep-copy a linked list where each node has both .next and a .random pointer. Vercel asks this for the interleaving trick that achieves O(1) extra space — the kind of pointer-arithmetic discipline they need in their runtime.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; O(1) space version is the bonus.
  • Blind (2026-Q1)— Listed in Vercel runtime engineer screen.

Problem

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state.

Constraints

  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • Node.random is null or is pointing to some node in the linked list.

Examples

Example 1

Input
head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output
[[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2

Input
head = []
Output
[]

Approaches

1. Hash map original -> clone

Two passes: first creates clones and the map; second rewires next and random.

Time
O(n)
Space
O(n)
function copyRandomList(head) {
  if (!head) return null;
  const map = new Map();
  for (let cur = head; cur; cur = cur.next) {
    map.set(cur, { val: cur.val, next: null, random: null });
  }
  for (let cur = head; cur; cur = cur.next) {
    map.get(cur).next = cur.next ? map.get(cur.next) : null;
    map.get(cur).random = cur.random ? map.get(cur.random) : null;
  }
  return map.get(head);
}

Tradeoff: Clean and correct. The interleaving trick gives O(1) extra space as the bonus.

2. Interleave + split, O(1) space (optimal)

Pass 1: interleave clones into the original list (A -> A' -> B -> B' -> ...). Pass 2: set each A'.random = A.random.next. Pass 3: split the two interleaved lists.

Time
O(n)
Space
O(1)
function copyRandomList(head) {
  if (!head) return null;
  // Pass 1: interleave
  for (let cur = head; cur; cur = cur.next.next) {
    const clone = { val: cur.val, next: cur.next, random: null };
    cur.next = clone;
  }
  // Pass 2: set random pointers
  for (let cur = head; cur; cur = cur.next.next) {
    if (cur.random) cur.next.random = cur.random.next;
  }
  // Pass 3: split
  const cloneHead = head.next;
  for (let cur = head; cur; cur = cur.next) {
    const clone = cur.next;
    cur.next = clone.next;
    if (clone.next) clone.next = clone.next.next;
  }
  return cloneHead;
}

Tradeoff: O(1) extra space. The interleaving makes A.random.next equal to A'.random (the clone we need).

Vercel-specific tips

Vercel grades the O(1) space version. Bonus signal: explaining the interleaving insight — putting the clone immediately after each original makes A.random.next always point to the corresponding clone. The three-pass structure is the canonical answer.

Common mistakes

  • Splitting before setting random pointers — A.random.next is no longer the clone after split.
  • Forgetting the null check on cur.random — crashes on `null.next`.
  • Restoring original list incorrectly in pass 3 — leaves it interleaved or mangled.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Linked list with multiple extra pointers — generalize the interleaving.
  • Deep-copy a graph instead (LC 133).
  • Recursive version — same map approach with recursion.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does interleaving give A.random.next = A'.random?

After interleaving, every original node A is immediately followed by its clone A'. If A.random points to X, then A'.random should point to X' — and X' is exactly X.next in the interleaved list.

When is the map version preferred?

When code clarity matters more than space. The interleaving version is O(1) space but harder to explain quickly. Both are O(n) time.

Practice these live with InterviewChamp.AI

Drill Copy List with Random Pointer and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →