Problem Statement

You are given a linked list where each node contains an additional random pointer. This pointer could point to any node in the list or be null.

Create a deep copy of this linked list. The deep copy should have n new nodes, where each new node's value matches the value of its corresponding node in the original list. Additionally, both the next and random pointers of the new nodes should point to the new nodes in the copied list.

The pointers in the copied list should maintain the same structure as the original list. None of the pointers in the new list should reference any node in the original list.

For instance, if in the original list, node X has a random pointer to node Y (X.random -> Y), then in the copied list, the corresponding nodes x and y should have a random pointer such that x.random -> y.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, randomIndex] where:

• val: It is an integer representing Node.val
• randomIndex: The index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Given a head of the linked list, return the head of the newly copied linked list.

Examples

Example 1:

• Input: head = [[3, 1], [4, null], [5, 0], [7, 2]]

• Output: [[3, 1], [4, null], [5, 0], [7, 2]]
• Explanation: The original list is cloned and returned.

Example 2:

• Input: head = [[1, 2], [2, 0], [3, 1]]

• Expected Output: [[1, 2], [2, 0], [3, 1]]
• Explanation: The original list is cloned and returned.

Example 3:

• Input: head = [[8, 2], [9, null], [7, 1]]

• Output: [[8, 2], [9, null], [7, 1]]
• Explanation: The original list is cloned and returned.

Constraints:

• 0 <= n <= 1000
• -10⁴ <= Node.val <= 10⁴
• Node.random is null or is pointing to some node in the linked list.

Try it yourself

Try solving this question here: