Clone a Linked List with Random Pointers

Given a linked list where each node contains two pointers: one pointing to the next node and another random pointer that can point to any node within the list (or be null), your task is to create a deep copy of this linked list and return the head of the copied list.

Explanation:

A deep copy of a linked list means creating entirely new nodes for each node in the original list without retaining any references to the nodes of the original linked list.

Input:

The first line of input contains an integer ‘T’, representing the number of test cases. Each test case consists of a single line containing elements of the linked list with random pointers, represented by node-value and random-index pairs separated by a space.

Each node is described as: Value RandomIndex, where Value is an integer denoting the node value, and RandomIndex is the index of the node where the random pointer is directed to, or -1 if it does not point to any node.

Output:

For each test case, output “True” if the linked list is successfully cloned, otherwise “False”. Each result should be on a separate line.

Example:

Input:
1
1 2 2 0 3 -1

Output:
True

Constraints:

• 1 ≤ T ≤ 10
• 0 ≤ N ≤ 5 * 104
• -105 ≤ data ≤ 105 and data ≠ -1
• -1 ≤ random_index < N

Note:

You do not need to print anything; the output handling is already taken care of. Please implement the function to create a deep copy of the linked list.