LeetCode 86. Partition List

November 23, 2024

I had to read the comments to understand this problem. I didn't understand how they wanted the ordering until I read a few examples.

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 partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
8        start = head
9        left, right = None, None
10
11        while head and not right:
12            if head.val < x:
13                left = head
14            else:
15                right = head
16            head = head.next
17        
18        prev = None
19        
20        while head:
21            if head.val < x:
22                if prev:
23                    prev.next = head.next
24                if left:
25                    left.next = head
26                    left = left.next
27                else:
28                    left = head
29                    start = left
30                if right.next == head:
31                    right.next = head.next
32                head.next = right
33
34            prev = head
35            head = head.next
36        
37        return start

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

LeetCode 82. Remove Duplicates from Sorted List II

LeetCode 146. LRU Cache