Skip to main content

89. Copy List with Random Pointer

mediumAsked at Workday

Deep-copy a linked list where each node has a random pointer to any other node. Workday uses this for two-pass-or-hash-map design — same shape as cloning an employee record graph with cross-references intact.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

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. Return the head of the copied linked 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->copy

Pass 1: create all copy nodes and store mapping. Pass 2: set next and random via 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) {
    map.get(cur).next = map.get(cur.next) || null;
    map.get(cur).random = map.get(cur.random) || null;
    cur = cur.next;
  }
  return map.get(head);
}

Tradeoff: Two passes, O(n) extra space. Straightforward.

2. Interleaved copy (O(1) extra)

Pass 1: interleave A -> A' -> B -> B' -> C -> C'. Pass 2: set A'.random = A.random.next. Pass 3: separate.

Time
O(n)
Space
O(1) extra)
// pass 1: insert copy after each original
// pass 2: copy.random = original.random?.next
// pass 3: detangle next pointers

Tradeoff: O(1) extra space but tricky to write under time pressure. Mention it as the optimization.

Workday-specific tips

Workday accepts the hash-map version as the primary. Mention the interleaved trick as the O(1)-space follow-up. Articulate why two passes are needed — random can point forward, so you can't set it on the first pass.

Common mistakes

  • Setting random in one pass — fails when random points to a node not yet copied.
  • Forgetting null handling for random.
  • Reusing the mapping incorrectly across passes.

Follow-up questions

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

  • Clone Graph (LC 133) — similar deep-copy pattern.
  • What if there are cycles via random?
  • Serialize/deserialize a list with random pointers.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Two passes?

Pass 1 ensures all copy nodes exist before we wire up references. Random can point to a node before or after — we need them all materialized first.

Recursive variant?

Use memoization on the map. Recursive deep-copy with cycle detection via map presence. Same complexity.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →