Given a singly linked list where each node contains an integer value and a random pointer that may 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 the value, next, and random pointers are preserved, but no pointer in the new list refers to any node in the original list. Return the head of the deep copied list. The input and output are represented as a list of [value, random_index] pairs, where random_index is the index of the node that the random pointer refers to, or None if it does not point to any node.
Example 1
Input: [[5,None],[8,0],[12,2],[7,1]]
Output: [[5,None],[8,0],[12,2],[7,1]]
Explanation: The copied list preserves the values and random pointer structure.
Example 2
Input: [[2,None],[4,None],[6,None]]
Output: [[2,None],[4,None],[6,None]]
Explanation: All random pointers are null.
Example 3
Input: [[9,2],[3,0],[1,1]]
Output: [[9,2],[3,0],[1,1]]
Explanation: Random pointers form a cycle among nodes.
Constraints
Case 1
Input: [[10,None],[20,0],[30,1]]
Expected: [[10,None],[20,0],[30,1]]
Case 2
Input: [[100,1],[200,None],[300,0]]
Expected: [[100,1],[200,None],[300,0]]
Case 3
Input: [[1,None]]
Expected: [[1,None]]
Case 4
Input: []
Expected: []