Skip to main content

138. Copy List with Random Pointer

mediumAsked at Shopify

Shopify uses Copy List with Random Pointer to test whether you can solve a deep-clone problem with a hash map first, then optimize to O(1) extra space with the interleaving trick. It mirrors real cloning needs in template/product structures with cross-references.

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

Source citations

Public interview reports confirming this problem appears in Shopify loops.

  • Glassdoor (2026-Q1)— Shopify Backend Developer + Senior Engineering interviews cite this as the standard linked-list-with-references question.
  • Reddit r/cscareerquestions (2025-11)— Shopify new-grad reports include this with the O(1) extra space follow-up.

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 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. Two-pass hash map (canonical)

Pass 1: walk the original list, creating a clone of each node and storing original->clone in a Map. Pass 2: walk again, wiring up clone.next and clone.random by looking up the originals in the Map.

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

Tradeoff: Two passes, O(n) extra map. The cleanest correct answer. Shopify accepts this if you discuss the O(1) space follow-up.

2. One-pass hash map with recursion

DFS-clone each reachable node lazily — if the clone exists in the map, reuse it; otherwise create and recurse.

Time
O(n)
Space
O(n) recursion + map
function copyRandomListRec(head) {
  const map = new Map();
  function clone(node) {
    if (!node) return null;
    if (map.has(node)) return map.get(node);
    const copy = { val: node.val, next: null, random: null };
    map.set(node, copy);
    copy.next = clone(node.next);
    copy.random = clone(node.random);
    return copy;
  }
  return clone(head);
}

Tradeoff: Same O(n) time and space. Recursion depth equals list length — up to 1000 frames, fine for the constraint but worth mentioning. Useful when the random graph has multiple pointers per node (generalizes naturally).

3. Interleaving trick (optimal O(1) extra space)

Pass 1: insert each clone immediately after its original (A->A'->B->B'->C->C'). Pass 2: set clone.random = original.random.next. Pass 3: detach the clone list from the original.

Time
O(n)
Space
O(1) excluding output
function copyRandomListInterleave(head) {
  if (!head) return null;
  // Pass 1: interleave clones
  let cur = head;
  while (cur) {
    const clone = { val: cur.val, next: cur.next, random: null };
    cur.next = clone;
    cur = clone.next;
  }
  // Pass 2: assign random pointers
  cur = head;
  while (cur) {
    if (cur.random) cur.next.random = cur.random.next;
    cur = cur.next.next;
  }
  // Pass 3: detach
  cur = head;
  const cloneHead = head.next;
  while (cur) {
    const clone = cur.next;
    cur.next = clone.next;
    clone.next = clone.next ? clone.next.next : null;
    cur = cur.next;
  }
  return cloneHead;
}

Tradeoff: Shopify's senior-bar answer. Three passes, NO hash map, O(1) extra space. The interleaving trick exploits the fact that clone[i] is the node right after original[i] — so original.random.next IS clone.random. Beautiful but error-prone; practice the detach step.

Shopify-specific tips

Shopify's expected dialogue: write the two-pass hash map version first; when asked 'can you do it without extra space?', pivot to the interleaving trick. Senior candidates should write the interleaving directly if they spot it. Volunteer the recursive version as a third option if the interview leaves time.

Common mistakes

  • Setting clone.random = original.random (a pointer to the ORIGINAL, not the clone). Must dereference to find the clone.
  • Forgetting the detach step in the interleaving version — leaves the original list interleaved.
  • Using the original node as a Map key by value — JavaScript Map uses reference equality, which is correct here but easy to confuse.
  • Returning the wrong head on empty input — must handle head === null first.

Follow-up questions

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

  • Clone an arbitrary graph (LeetCode 133).
  • Clone a tree with parent pointers.
  • Serialize and deserialize a linked list with random pointers (LeetCode 297 variant).
  • What if random can point to nodes not in this list (cross-list references)?
  • What if nodes have multiple random pointers (a list of refs)?

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 interleaving trick work?

Because after pass 1, clone[i] is always at position 2i+1 (one after original[i]). So original[i].next is clone[i], and original[i].random.next is the clone of original[i].random — which is exactly the random pointer we want for clone[i].

Hash map vs interleaving — which to ship?

Hash map is the safer default — shorter code, lower bug surface. Interleaving wins only when the O(1) space constraint is explicit. Shopify accepts either; ship hash map unless asked to optimize.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →