Skip to main content

138. Copy List with Random Pointer

mediumAsked at Microsoft

Copy List with Random Pointer is Microsoft's classic deep-clone test. The trick is mapping each original node to its clone so the random pointer (which might point forward into yet-uncloned territory) lands on the right copy. Two passes with a hash map is the standard answer; O(1) space with interleaving is the bonus.

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

Source citations

Public interview reports confirming this problem appears in Microsoft loops.

  • Glassdoor (2026-Q1)— Microsoft Azure org onsite reports repeatedly cite this as the 30-minute linked-list deep-clone medium.
  • Blind (2025-11)— Multiple Microsoft L60 2025 reports list Copy List with Random Pointer.

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. 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 original -> clone (two passes)

First pass: create the cloned node for every original and store original -> clone in a map. Second pass: wire next and random on each clone using the map.

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

Tradeoff: Two linear passes, O(n) extra space. This is the answer Microsoft expects you to write — clean separation between 'make all the nodes' and 'wire up the pointers using the map as a translator.'

2. Interleave clones, then split (optimal O(1) extra)

Insert each clone right after its original (so the list becomes A -> A' -> B -> B' -> ...). Set each clone.random = original.random.next (the clone next to the random target). Final pass: detach the cloned chain.

Time
O(n)
Space
O(1) excluding output
function copyRandomList(head) {
  if (!head) return null;
  let curr = head;
  while (curr) {
    const clone = { val: curr.val, next: curr.next, random: null };
    curr.next = clone;
    curr = clone.next;
  }
  curr = head;
  while (curr) {
    if (curr.random) curr.next.random = curr.random.next;
    curr = curr.next.next;
  }
  const newHead = head.next;
  curr = head;
  while (curr) {
    const clone = curr.next;
    curr.next = clone.next;
    clone.next = clone.next ? clone.next.next : null;
    curr = curr.next;
  }
  return newHead;
}

Tradeoff: Three passes but O(1) extra space — the cloned list IS the auxiliary structure. Microsoft interviewers love asking for this as a follow-up after the hash-map version lands.

Microsoft-specific tips

Microsoft interviewers explicitly grade whether you can articulate the random-pointer problem out loud: 'random can point forward to nodes I haven't cloned yet, so I either pre-create everything (hash map) or I weave the clones in so each random target's clone is exactly one hop away.' Saying that sentence before writing code separates clear thinkers from candidates who write the hash map by rote.

Common mistakes

  • Forgetting to handle node.random === null in the wiring pass — calling map.get(null) returns undefined and crashes the next dereference.
  • In the interleave version, forgetting to restore the original list — Microsoft sometimes asks for this explicitly.
  • Returning head instead of map.get(head) in the hash-map version.

Follow-up questions

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

  • Clone Graph (LC 133) — same hash-map-then-wire pattern on a graph.
  • Clone N-ary Tree (LC 1490) — extension to trees.
  • Linked List Cycle (LC 141) — pointer-manipulation drill.

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 random pointer make this hard?

Because it can point forward to a node that doesn't have a clone yet. You either pre-create every clone (hash map) or you wire the originals and clones together so the lookup is O(1).

How often does Microsoft ask the O(1) version?

About half the time. The hash-map version is always accepted; the interleave-and-split version is a follow-up if there's time left. Practicing both is worth it.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →