Skip to main content

138. Copy List With Random Pointer

mediumAsked at Amazon

Deep-copy a linked list with both next and random pointers. Amazon asks this to test the hash-map clone pattern and (for senior IC) the O(1)-space interleave trick.

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

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE II onsite reports cite this as the linked-list deep-copy problem.
  • Blind (2025-11)— Recurring Amazon interview question.

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.

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]]

Approaches

1. Two-pass hash map

Pass 1: create clone for each original; map orig -> clone. Pass 2: wire next/random.

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

Tradeoff: Most common interview answer. Two passes, clear correctness.

2. Interleave + split (O(1) extra space)

Insert clones right after each original. Wire random via clone.random = original.random.next. Split into two lists at the end.

Time
O(n)
Space
O(1) extra
function copyRandomList(head) {
  if (!head) return null;
  let node = head;
  while (node) {
    const clone = { val: node.val, next: node.next, random: null };
    node.next = clone;
    node = clone.next;
  }
  node = head;
  while (node) {
    if (node.random) node.next.random = node.random.next;
    node = node.next.next;
  }
  node = head;
  const dummy = { val: 0, next: null };
  let cloneTail = dummy;
  while (node) {
    cloneTail.next = node.next;
    cloneTail = cloneTail.next;
    node.next = node.next.next;
    node = node.next;
  }
  return dummy.next;
}

Tradeoff: O(1) extra space. Mutates the original list temporarily then restores it. Three passes but each is linear.

Amazon-specific tips

Amazon interviewers grade on two axes: (1) you reach for the map version; (2) you mention the interleave trick as the O(1)-space optimization. Articulating the interleave invariant — 'every clone is at original.next, so original.random.next is the clone of original.random' — is the senior-IC signal.

Common mistakes

  • Forgetting null checks for random pointers.
  • In the interleave: forgetting to restore the original list in pass 3.
  • Confusing iteration step in pass 2 (node = node.next.next, not node = node.next).

Follow-up questions

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

  • Clone Graph (LC 133) — same map pattern.
  • Clone N-ary Tree.
  • What if random pointed to a node in a different list?

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 interleave work?

After interleaving, every original node has its clone at original.next. So original.random.next is exactly the clone of original.random — which is what the clone's random should point to.

Map version or interleave — which does Amazon prefer?

Map first (clear and obvious). Offer interleave as the optimization. Most interviewers count map as sufficient; interleave is bonus.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →