0138 Copy List with Random Pointer

Question

My Solution:

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        # create a hashmap to map the old node to new node
        # store {None: None} as edge case
        oldToCopy = {None: None} 

        # first pass: 
        # 1. create all nodes and
        # 2. map the olf node to the new node
        cur = head
        while cur:
            copy = Node(cur.val)
            oldToCopy[cur] = copy
            cur = cur.next

        # second pass:
        # 1. link the next
        # 2. link the random 
        cur = head
        while cur:
            copy = oldToCopy[cur]
            copy.next = oldToCopy[cur.next]
            copy.random = oldToCopy[cur.random]
            cur = cur.next
        
        return oldToCopy[head]