Given a singly linked list where each node contains an integer value and an additional random pointer that can point to any node in the list or be null, create a deep copy of the list. The deep copy must consist of new nodes such that for each original node, its value, next pointer, and random pointer are replicated in the copied list, but all pointers reference only nodes in the new list. Return the head of the copied linked list.
Example 1
Input: head = [[5,2],[8,null],[12,0],[7,1]]
Output: [[5,2],[8,null],[12,0],[7,1]]
Explanation: The copied list has the same structure as the original, with all pointers referencing new nodes.
Example 2
Input: head = [[4,null],[6,0]]
Output: [[4,null],[6,0]]
Explanation: Second node's random pointer points to the first node.
Example 3
Input: head = []
Output: []
Explanation: Empty list returns empty copy.
Constraints
Case 1
Input: head = [[9,1],[2,null],[5,0]]
Expected: [[9,1],[2,null],[5,0]]
Case 2
Input: head = [[1,null],[2,0],[3,1],[4,2]]
Expected: [[1,null],[2,0],[3,1],[4,2]]
Case 3
Input: head = [[10,null]]
Expected: [[10,null]]