Copy List with Random Pointer

You are given the head of a linked list of length n in which every node has two pointers:

• next, which points to the following node (or None at the tail), and
• random, which can point to any node in the list, including the node itself, or be None.

Return the head of a deep copy of the list: n brand-new nodes with the same values, where each copy's next and random point to the corresponding *copied* nodes. No pointer in the copy may refer to a node of the original list, and the original list must be left unchanged when you return.

How lists are written: in the examples, a list is shown as an array of [val, random_index] pairs from head to tail, where random_index is the 0-based position of the node that random points to, or None. The node class is:

class Node:
    def __init__(self, x, next=None, random=None):
        self.val = x
        self.next = next
        self.random = random