Skip to content
BASA DSA

Copy List With Random Pointer

MediumLinked List

Create a deep copy of a linked list with next and random pointers. Each random pointer targets any node in the list or null. Preserve values and all edges, using entirely new nodes. Input is an array of [value, randomIndexOrNull] pairs.

Example 1

Argument 1: next pointers; dashed arrows are random pointers.Argument 1: next pointers; dashed arrows are random pointers. Vertices: node 0: 4, node 1: 9, node 2: 7. Edges: node 0 (4) → node 1 (9); node 1 (9) → node 2 (7); node 0 (4) → node 2 (7) (random) random; node 1 (9) → node 0 (4) (random) random.randomrandom497
Argument 1: next pointers; dashed arrows are random pointers.

Input
head = [[4,2],[9,0],[7,null]]
Output
[[4,2],[9,0],[7,null]]

Explanation

Copy the chain and random edges 0->2, 1->0, 2->null into fresh nodes.

Example 2

Argument 1: next pointers; dashed arrows are random pointers.Argument 1: next pointers; dashed arrows are random pointers. Vertices: node 0: 2. Edges: node 0 (2) → node 0 (2) (random) random.random2
Argument 1: next pointers; dashed arrows are random pointers.

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

Explanation

The copied node's random pointer must refer to itself, not the original.

Example 3

Argument 1: next pointers; dashed arrows are random pointers. No nodes or connections.
Input
head = []
Output
null

Explanation

A null head copies to null without allocation.

Constraints

  • 0 <= number of nodes <= 1000
  • random indices are zero-based and valid
  • next follows array order

Function contractcopyRandomListArguments: randomList
Loading draft…
SolutionRuns on your device