Linked Lists Reversing and rewiring
303. Copy List with Random Pointer
You are given head, the first node of a linked list in which every node has two pointers. next points to
the following node, as in any singly linked list, and is null on the last node. random points to any node
of the list, or to the node itself, or is null.
Return a deep copy of the list: a new node for every node of the list, with the same value. Each new
node's next and random point to the new nodes that stand where the old node's next and random point.
No pointer of the copy may point to a node of the given list, and the given list must be as it was when your
function returns.
The examples write a list as one [val,randomIndex] pair per node, from the head on. randomIndex is the
position of the node that random points to, counting from 0 at the head, or -1 when random is null.
Example 1 below, head = [[7,2],[13,0],[7,-1],[2,3]], is this list. The solid arrows are next and the
dashed arrows are random:
The output shows the copy you return the same way, finding each random by its position in your copy.
Example 1
Input: head = [[7, 2], [13, 0], [7, -1], [2, 3]]
[[7,2],[13,0],[7,-1],[2,3]]Explanation: The first node holds 7, and its random points to the other 7, at position 2. In the copy, the first
node's random points to the copy's third node. The last node points to itself, and so does its copy.
Example 2
Input: head = [[-4, 0], [-4, 0]]
[[-4,0],[-4,0]]Explanation: Both nodes hold -4, and both random pointers point to the head, so the head points to itself. Both
new nodes point to the new head.
Example 3
Input: head = []
[]Explanation: An empty list has nothing to copy, so the answer is null.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109Node.randomis null or a node of the list. In a test,-1 ≤ randomIndex ≤ number of nodes − 1; any other index means null.
Clarifying questions
What you would ask an interviewer before writing any code.