Skip to main content

138. Copy List With Random Pointer

mediumAsked at Meta

Deep-copy a linked list where each node has a random pointer in addition to next. Meta asks this to test whether you can handle the two-pass map approach or the elegant O(1)-space interleaving trick.

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

Source citations

Public interview reports confirming this problem appears in Meta loops.

  • Glassdoor (2026-Q1)— Meta E4 onsite reports cite this as a recurring linked-list problem.
  • Blind (2025-09)— Recurring Meta interview problem.

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

Approaches

1. Two-pass hash map (optimal whiteboard)

Pass 1: create a clone for each node, mapping original to clone. Pass 2: wire up next and random via the map.

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: Two passes, clean and obvious. The map provides O(1) lookup from original to clone.

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

Insert each clone right after its 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;
  // Pass 1: interleave clones
  let node = head;
  while (node) {
    const clone = { val: node.val, next: node.next, random: null };
    node.next = clone;
    node = clone.next;
  }
  // Pass 2: wire random pointers
  node = head;
  while (node) {
    if (node.random) node.next.random = node.random.next;
    node = node.next.next;
  }
  // Pass 3: split
  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 by piggy-backing the clone right after the original. Mutates the original list temporarily — must restore it in pass 3.

Meta-specific tips

Meta interviewers grade this on two axes: (1) you reach for the map version first (correct, clear); (2) you OFFER the O(1)-space interleave trick as an optimization. The interleave trick is elegant — describing it before coding is the senior-IC signal even if you don't write all three passes flawlessly.

Common mistakes

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

Follow-up questions

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

  • Clone an N-ary tree.
  • Clone a graph (LC 133) — same map pattern.
  • 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 the interleave trick work?

After interleaving, every original node's clone is 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 Meta prefer?

Map version is the default. Interleave scores higher on senior-IC bars because it shows you can find O(1)-space optimizations. Lead with map, then offer interleave.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →