Copy List with Random Pointer

Each node of this linked list has a next pointer and a random pointer, which may point to any node of the list or to null. Make a deep copy: brand-new nodes with the same values, whose next and random pointers point to the corresponding new nodes.

Input:

• line 1: n
• line 2: the n values
• line 3: n numbers — for node i, the 0-based index of the node its random pointer points to, or -1 for null

Output: walk your copy and print two lines:

• line 1: the values along next
• line 2: for every node, the value of the node its random points to (or null)

Constraints: 1 ≤ n ≤ 2·10⁴, −10⁴ ≤ value ≤ 10⁴.

Two classic solutions: a hash map from old node → new node (two passes), or the O(1)-memory trick of weaving each copy right after its original (A → A' → B → B' …), setting randoms, then unweaving.