Deep copy a linked list with random pointers.
O(n)
def copyRandomList(head): oldToCopy = {None: None} curr = head while curr: copy = Node(curr.val) oldToCopy[curr] = copy curr = curr.next curr = head while curr: copy = oldToCopy[curr] copy.next = oldToCopy[curr.next] copy.random = oldToCopy[curr.random] curr = curr.next return oldToCopy[head]