This problem was tricky as I had to track Node references rather than the index given in the input.

Solution

Copy
1from collections import defaultdict
2"""
3# Definition for a Node.
4class Node:
5    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
6        self.val = int(x)
7        self.next = next
8        self.random = random
9"""
10
11class Solution:
12    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
13        start = Node(head.val) if head else None
14        node = start
15        randoms = defaultdict(list)
16        nodes = {}
17        while head:
18            nodes[head] = node
19            node.next = Node(head.next.val) if head.next else None
20            node.val = head.val
21            if head.random:
22                randoms[head.random].append(head)
23            head = head.next
24            node = node.next
25        
26        for val in randoms.keys():
27            for neighbor in randoms[val]:
28                nodes[neighbor].random = nodes[val]
29
30        return start

O(n) = n since worst case is 2n due to the while loop, then at most visiting each node again when assigning the randoms' value.