Clone Linked List with Random Pointer

Your task is to create a deep copy of a linked list, where each node has two pointers: one that points to the next node in the list, and a 'random' pointer which can point to any node in the list or be null. The function should return the head of the newly created deep copied linked list.

A deep copy signifies creating new instances for each node rather than copying references from the original list.

Input:

Each test case begins with an integer T, the number of test cases. Following this, each test case includes a line with space-separated pairs representing the nodes of the linked list. Each pair consists of two integers: the node's value and the index it randomly points to. Use -1 for null next or random pointers. A test case may look like:
"1 2 2 0 3 4 4 4 5 1 -1"

Output:

For each test case, the output is "true" if the linked list has been successfully and correctly cloned. Output each result on a new line.

Example:

Explanation:

The line represents nodes with values and indexes their random pointers reference. For example, node 1 has a random pointer to node at index 2, node 2 points randomly to index 0, etc. Once processed, "true" indicates success.

Constraints:

• 1 <= T <= 10²
• 0 <= N <= 10³
• 0 <= DATA <= 10⁶ and data ≠ -1
• -1 <= RANDOMINDEX < N

Note:

It's not required to print anything manually; just implement the required function to deliver the correct outputs.