Deep Copy of Circular Linked List with Random Pointers

Problem Statement:

You are given a circular singly linked list where each node contains an integer value and a random pointer which may point to any node in the list or be null. The next pointers form a circle (i.e. the next pointer of the last node points to the first node). Your task is to create a deep copy of this linked list. All the nodes in the copied list must have exactly the same values, next pointers, and random pointer relationships as the original list.

It is important that the deep copy is completely independent of the original list. Use appropriate data structures to maintain the node relationships during the copy process. For example, consider a list of three nodes with values 1, 2, 3 and random pointer mappings: 1 → 3, 2 → 1, 3 → 2, and with the next pointers forming a cycle (1 → 2 → 3 → 1). The resulting deep copy must preserve both the circularity and the random pointer assignments.

Mathematically, if (L) is the list, then for each node (v \in L) with a random pointer (r(v)), the deep copy (L') must satisfy (\forall v \in L,\ r(v) = w \Rightarrow r(v') = w'), where (v') and (w') are the corresponding nodes in (L'>.

inputFormat

Input Format:

The first line contains an integer (n) representing the number of nodes in the list ((n \ge 0)). If (n = 0), the list is empty.
If (n > 0), the second line contains (n) space-separated integers representing the values of the nodes.
The third line contains (n) space-separated integers where the (i)-th integer indicates the 0-indexed node that the (i)-th node's random pointer points to, or -1 if the random pointer is null.

Note: The linked list is circular, meaning the next pointer of the last node points back to the first node.

outputFormat

Output Format:

For a non-empty list ((n > 0)), output (n) lines. Each line should contain three space-separated integers: the node's index (starting from 0 in the cloned list), the node's value, and the index of the node to which its random pointer points (or -1 if it is null). The nodes should be output in the order of traversal following the next pointers starting from the head of the cloned list.

If the list is empty ((n = 0)), output nothing.## sample

0