Clone Linked List with Random Pointer Problem Statement

Given a linked list where each node has two pointers: one pointing to the next node and another which can point randomly to any node in the list or null, your task is to create a deep copy of this linked list and return its head. The validation will be done to ensure the cloned linked list is an exact copy of the original.

Explanation:

A deep copy means creating new nodes rather than copying references of the original linked list's nodes.

Example:

Consider the following illustration where random pointers are shown in red and next pointers in black:

Input:

The first line contains an integer ‘T’, the number of test cases.
Each test case consists of a single line with nodes (value and random pointer index) separated by spaces. -1 is used for null values.
Each node is represented as a pair:
- Value: an integer for node value
- Random index: index for the node the random pointer points to or -1 if it's null

Output:

For each test case, output "true" if the linked list is successfully cloned.
Each output is on a new line for separate test cases.

Constraints:

• 1 <= T <= 10^2
• 0 <= N <= 10^3 (where N is the number of nodes)
• 0 <= DATA <= 10^6 and DATA != -1
• -1 <= RANDOMINDEX < N

Each node is represented by [value, randomIndex] format, end of the list denoted by [-1].

Note:

You are required to implement the function; printing is handled separately.

Follow-up:

Can the cloning be accomplished without utilizing extra space?