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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        start = head
        left, right = None, None

        while head and not right:
            if head.val < x:
                left = head
            else:
                right = head
            head = head.next
        
        prev = None
        
        while head:
            if head.val < x:
                if prev:
                    prev.next = head.next
                if left:
                    left.next = head
                    left = left.next
                else:
                    left = head
                    start = left
                if right.next == head:
                    right.next = head.next
                head.next = right

            prev = head
            head = head.next
        
        return start

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