Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

The order of the initial linked list must be preserved.


from copy import deepcopy
class Solution:
    def add_to_list(self, head, node,x): = None
        if head is None and node.val < x:
            self.left_part = node
            self.left_tail = node
        elif head is None and node.val >= x:
            self.right_part = node
            self.right_tail = node
        if head == self.left_part:
   = node
            self.left_tail = node
        if head == self.right_part:
   = node
            self.right_tail = node
    def partition(self, head: ListNode, x: int) -> ListNode:
        self.left_part = None
        self.right_part = None
        tmp = head
        while tmp:
            tmp_cpy = deepcopy(tmp)
            if tmp.val < x:
                self.add_to_list(self.left_part, tmp_cpy,x)
                self.add_to_list(self.right_part, tmp_cpy,x)
            tmp =
        tmp = self.left_part
        if not tmp:
            return self.right_part = self.right_part
        return self.left_part

Time complexity: O(n)
Space complexity: O(1)