Copy List With Random Pointer

Medium · Linked List

You are given the head of a linked list where each node has an integer value, a pointer to the next node, and an extra pointer called random that can point to any node in the list or to null. Build a completely separate copy of this list, with new nodes, so that the structure and all next and random links mirror the original exactly, and return the head of this new list. The copy must not share any node objects with the original list.

Examples

Input:  head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Why:    Each node's value and its next/random targets (given as indices into the list) are reproduced identically in the new list of brand new node objects.

Input:  head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Why:    Node 0's random points to node 1 and node 1's random points to itself; the copy preserves both relationships with new nodes.

Input:  head = []
Output: []
Why:    An empty list copies to an empty list.

Constraints

0 <= number of nodes <= 1000, -10^4 <= node.val <= 10^4, random is either null or points to some node in the list (possibly itself)

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Copy List With Random Pointer

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Copy List With Random Pointer. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.