Solutions

# Hashmap. Or recursive + hashmap.
# linked-lists

# Hashmap - O(n) time, O(n) space
def copyRandomList(head: 'Optional[Node]') -> 'Optional[Node]':
    hashmap = {None: None} # old to new map
    cur = head
    while cur:
        newnode = Node(cur.val)
        hashmap[cur] = newnode
        cur = cur.next

    cur = head
    while cur:
        hashmap[cur].next = hashmap[cur.next]
        hashmap[cur].random = hashmap[cur.random]
        cur = cur.next

    return hashmap[head]


# Recursive + hashmap - O(n) time, O(n) space
map = {}
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
    if head is None:
        return None
    if head in self.map:
        return self.map[head]

    copy = Node(head.val)
    map[head] = copy
    copy.next = copyRandomList(head.next)
    copy.random = map.get(head.random)
    return copy