LeetCode 82. Remove Duplicates from Sorted List II

November 21, 2024

The trick for this one was tracking duplicates via the unique boolean and a pending variable.

Solution

Copy
1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, val=0, next=None):
4#         self.val = val
5#         self.next = next
6class Solution:
7    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
8        start = None
9        curr = None
10        pending = None
11        unique = True
12        while head:
13            if not pending:
14                pending = head
15            elif pending.val != head.val and unique:
16                if not start:
17                    start = pending
18                    curr = start
19                else:
20                    curr.next = pending
21                    curr = curr.next
22                pending = head
23            elif pending.val != head.val and not unique:
24                pending = head
25                unique = True
26            else:
27                unique = False
28                if curr:
29                    curr.next = None
30            head = head.next
31        
32        if pending and unique:
33            if start:
34                curr.next = pending
35            else:
36                start = pending
37
38        return start

Time complexity is O(n) = n and space complexity is O(1).

LeetCode 100. Same Tree

LeetCode 86. Partition List