Copy List with Random Pointer

A linked list has nodes with a val, a next pointer and a random pointer that points to any node of the list or to null. Make a deep copy of it: new nodes, with next and random pointers that point only to nodes of the copy.

The judge describes the original list with two arrays: vals[i] is the value of node i, and randomIdx[i] is the index of the node that node i's random pointer points to, or -1 for null. Build the list yourself from these arrays (for example with a small Node class with val, next, random), copy it, and return the copy in the same form: an array of [val, randomIndex] pairs, one per node in list order, where randomIndex is the index of the target of the copy's random pointer (or -1).

Do not read the answer straight from the input arrays; the point is to implement the copy over real nodes.