Skip to main content

69. Copy List with Random Pointer

mediumAsked at Datadog

Deep-copy a linked list where each node has both a next pointer and a random pointer to any node. Datadog uses this for the old-to-new mapping trick — same shape as their snapshot logic for a graph with arbitrary edges.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — graph cloning analog.

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

Example 2

Input
head = [[1,1],[2,1]]
Output
[[1,1],[2,1]]

Approaches

1. Two-pass with Map<original, copy>

Pass 1: create copies, store mapping. Pass 2: wire next and random via 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) {
    map.get(curr).next = map.get(curr.next) || null;
    map.get(curr).random = map.get(curr.random) || null;
    curr = curr.next;
  }
  return map.get(head);
}

Tradeoff: O(n) extra memory. Datadog accepts this; some interviewers push for O(1).

2. Interleave + un-interleave in place (optimal-space)

Step 1: insert each copy directly AFTER its original. Step 2: set copy.random = orig.random.next. Step 3: separate the two lists.

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

Tradeoff: O(1) extra space (just pointer manipulation). The interleave trick is the Datadog-canonical zero-overhead clone — same shape as their in-place snapshot transformation.

Datadog-specific tips

Datadog grades on whether you reach for the interleave trick when asked for O(1) space. The hashmap version is the entry-level answer. Bonus signal: discuss when the hashmap version is preferable (when the original list must not be temporarily modified).

Common mistakes

  • In the interleave version, forgetting that copy.random is set via curr.random.next (NOT curr.random) — the copy lives at curr.random.next.
  • Forgetting the null check on random — crashes on null randoms.
  • Failing to separate the lists at the end — leaves the original list with copies interleaved.

Follow-up questions

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

  • Clone Graph (LC 133) — same map-based approach.
  • Datadog-style: snapshot a graph with arbitrary edges in O(1) extra space.
  • Cycle detection in this list — Floyd's still works.

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 curr.random.next point to the copy?

After interleaving, every original is followed by its copy. So curr.random.next is the COPY of whatever curr.random points to — exactly what we want for copy.random.

When is hashmap better?

When the input must remain pristine during cloning (can't temporarily mutate). The hashmap version reads-only.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →