Skip to main content

138. Copy List with Random Pointer

medium

Deep-copy a linked list where each node has an extra pointer to a random node anywhere in the list. The interleaving trick replaces the natural hash map with O(1) extra space — slick to derive on the spot.

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

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

Example 3

Input
head = []
Output
[]

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Hash map approach: in pass 1 create every clone and map original -> clone. In pass 2 wire clone.next = map[orig.next] and clone.random = map[orig.random]. O(n) time AND O(n) space.

Hint 2

For O(1) extra space: interleave clones into the original list — every original node is followed by its clone.

Hint 3

With clones interleaved, clone.random is just orig.random.next. Finally, split the two lists back apart.

Solution approach

Reveal approach

Interleave-then-split. Pass 1: walk the original list; for each node A insert a new node A' right after it (A -> A' -> B -> B' -> ...). Pass 2: walk the interleaved list; for each clone, set clone.random = orig.random.next (which is orig.random's clone) — null-safe. Pass 3: detach the clones into their own list by walking and rewriting next pointers — restore each original's next to skip its clone, set each clone's next to the next clone. Return the head of the clone list. O(n) time, O(1) extra space beyond the output.

Complexity

Time
O(n)
Space
O(1) (excluding the output)

Related patterns

  • linked-list
  • hash-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Copy List with Random Pointer and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →