class Solution:

    # def __init__(self):
    #     self.visited_hash_map = dict()

    # def copyRandomList(self, head: 'Node') -> 'Node':

    #     if not head: return head

    #     if head in self.visited_hash_map:
    #         return self.visited_hash_map[head]

        
    #     head_cp = Node(head.val)
    #     self.visited_hash_map[head] = head_cp

    #     head_cp.next = self.copyRandomList(head.next)
    #     head_cp.random = self.copyRandomList(head.random)

    #     return head_cp


    def copyRandomList(self, head: 'Node') -> 'Node':

        if not head: return head

        visited_hash_map = dict()

        node = head
        
        while node:

            # copy self
            if node not in visited_hash_map:
                visited_hash_map[node] = Node(node.val)
            
            # next
            if node.next not in visited_hash_map:
                visited_hash_map[node.next] = Node(node.next.val) if node.next else None
            visited_hash_map[node].next =  visited_hash_map[node.next]

            # random
            if node.random not in visited_hash_map:
                visited_hash_map[node.random] = Node(node.random.val) if node.random else None
            visited_hash_map[node].random = visited_hash_map[node.random] 

            node = node.next
        
        return visited_hash_map[head]