Copy List with Random Pointer

medium

A linked list of length n is given, where each node contains an additional random pointer that can point to any node in the list, or to null.

Construct a deep copy of the list. Each node in the new list should have its val set, and its next and random pointers should point to new nodes in the copied list — never to nodes in the original list.

Return the head of the copied linked list.

Test Cases

Copy an input into the main harness and Run to verify

Input

head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Expected Output

[[7,null],[13,0],[11,4],[10,2],[1,0]]

Explanation: Each pair is [val, index of the random target].

Input

head = [[1,1],[2,1]]

Expected Output

[[1,1],[2,1]]

Constraints

0 <= n <= 1000
-10^4 <= Node.val <= 10^4
Node.random is null or points to some node in the list.

Hints

Hint 1 — click to reveal

The hard part is that a random pointer may target a node you have not created yet.

Hint 2 — click to reveal

A map from original node to copied node solves it. Can you avoid the map by interleaving copies into the original list?

Java Compiler