76. Copy List with Random Pointer

mediumAsked at Plaid

Deep copy a linked list where each node has a random pointer to any other node. Plaid asks this because cloning an entity graph with cross-references (transactions pointing to merchants pointing to categories) uses the same pattern.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Plaid loops.

Glassdoor (2025)— Plaid backend onsite — entity-graph cloning variant.
LeetCode Discuss (2026)— Plaid SWE II OA.

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. None of the pointers in the new list should point to nodes in the original 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]]

Example 2

Input

head = [[1,1],[2,1]]

Output

[[1,1],[2,1]]

Approaches

1. Hash map old-to-new

First pass: create new nodes, map old->new. Second pass: wire up next and random.

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

function copyRandomList(head) {
  const map = new Map();
  for (let p = head; p; p = p.next) map.set(p, { val: p.val, next: null, random: null });
  for (let p = head; p; p = p.next) {
    map.get(p).next = p.next ? map.get(p.next) : null;
    map.get(p).random = p.random ? map.get(p.random) : null;
  }
  return head ? map.get(head) : null;
}

Tradeoff: Two passes, clear. The map handles the random-pointer resolution.

2. Interleave-and-split

Insert each new node right after its original. Wire random pointers using node.next. Then split.

Time: O(n)
Space: O(1)

function copyRandomList(head) {
  if (!head) return null;
  // 1. interleave
  for (let p = head; p; p = p.next.next) {
    p.next = { val: p.val, next: p.next, random: null };
  }
  // 2. set random
  for (let p = head; p; p = p.next.next) {
    if (p.random) p.next.random = p.random.next;
  }
  // 3. split
  const newHead = head.next;
  for (let p = head; p; p = p.next) {
    const c = p.next;
    p.next = c.next;
    c.next = c.next ? c.next.next : null;
  }
  return newHead;
}

Tradeoff: O(1) extra space. The interleave trick uses the original list's next pointers as the hash map. Three clear passes.

Plaid-specific tips

Plaid grades the hash-map version first (clarity), the interleave version second (memory). Bonus signal: discuss when O(1) extra space matters — when the list represents a large entity graph and the cloner is invoked frequently in a hot loop.

Common mistakes

Wiring next and random in the same pass without first creating all nodes — random.next would point to non-yet-cloned nodes.
Breaking the original list in the interleave version without restoring it.
Forgetting to handle p.random === null.

Follow-up questions

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

Clone an undirected graph (LC 133).
Clone a binary tree with parent pointers.
Serialize and clone an entire entity graph with multiple node types.

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 two passes (or three)?

Random pointers can target any node, so all clones must exist before random can be wired. Otherwise random.next would be undefined for forward references.

When prefer interleave over hash map?

When memory is tight and the list is huge. The interleave version uses the original list as the hash map.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →