The Runtime Theory
mediumLeetCode#hash-map#graph-copy

Copy List with Random Pointer

Create a deep copy of nodes whose next and random pointers may refer to any node in the list.

The Runtime Theory Team25 min read
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

innodes=[(7,null)]

out[(7,null)]

innodes=[(1,1),(2,0)]

outsame serialized values and random indexes, with new node identities

innodes=[]

out[]

Create a deep copy of nodes whose next and random pointers may refer to any node in the list.

A good solution should

  • State the invariant or decision rule that makes the approach correct.
  • Explain the time and space complexity in terms of the input sizes and required output.
  • Handle empty, minimal, duplicate, and boundary-shaped inputs covered by the contract.

Reasoning prompt

Do not reuse original nodes. Compare a two-pass map from original to copy with the interleaving technique.

Use the linked judge for the canonical problem. The examples above are compact TRT checks; write additional cases before submitting, especially for the boundary that tends to break your chosen invariant.

More practice in this topic

medium · linked listsAdd Two Numbersmedium · linked listsFind the Duplicate Numbereasy · linked listsLinked List Cycle

One dispatch a week

The trace behind each problem, the tradeoff that explains it, and one technical dispatch per week — no noise.

One technical dispatch per week. No noise.

Not started

Sign in to save your learning progress.

Sign in to save