LeetCode 138. Copy List with Random Pointer

November 15, 2024

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

Solution

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.

LeetCode 224. Basic Calculator

LeetCode 92. Reverse Linked List II