138. Copy List with Random Pointer

To copy a list with a random pointer, we’ll do two traversals.

First, we’ll do one pass to create a copy of each node in the list in a cache which holds its copy. Next, we’ll traverse again, but next time, set each copy’s next and random pointers to the copies in the list.

Finally, return the copy that refers to the head pointer.

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        cache = {None: None}
        curr = head
        
        while curr:
            cache[curr] = Node(curr.val)
            curr = curr.next
            
        curr = head
        
        while curr:
            copy = cache[curr]
            copy.next = cache[curr.next]
            copy.random = cache[curr.random]
            curr = curr.next
            
        return cache[head]