Every node of this linked list has two pointers: next, to the node after it, and random, which may point to any node of the list (itself included) or to nothing.
Given the head of the list, build a deep copy and return the head of the copy. A deep copy is made of brand-new nodes only, one per original, with the same values in the same order. Each copy's next and random must point to copies, mirroring the original: if original node X has random pointing to Y, then the copy of X has random pointing to the copy of Y. Not one pointer of the copy may reach a node of the original list, and the answer is rejected as "not a copy" if one does.
How lists are written here. A list of n nodes is written as n pairs [val, r], head first. val is the node's value and r is the position (counting from 0 at the head) of the node its random points to, or null when it points to nothing. [] is an empty list: you are given nothing (None/null/nil) and return nothing. Your answer is written back the same way.
Example 1
Input: head = [[5,null],[8,3],[-2,0],[11,1]]
Output: [[5,null],[8,3],[-2,0],[11,1]]
The head 5 has no random pointer. 8 points ahead to 11 (position 3), -2 points back to the head, and 11 points back to 8. The copy has the same four values with the same pointers, between its own nodes.
Example 2
Input: head = [[4,1],[4,1],[4,null]]
Output: [[4,1],[4,1],[4,null]]
All three values are 4, so a value doesn't tell you which node a pointer aims at. The first two nodes both point to the middle one.
Example 3
Input: head = [[0,0]]
Output: [[0,0]]
A single node whose random points to itself. Its copy must point to the copy, not to the original.
Constraints
0 and 1000 nodes.-10⁴ <= Node.val <= 10⁴random is null or points to a node of the same list.The hard part is random: when you copy a node, the node its random points to may not have a copy yet. Make every copy first, then wire the pointers.
[[5,null],[8,3],[-2,0],[11,1]]
[[5,null],[8,3],[-2,0],[11,1]]