Partition List

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.

You should preserve the original relative order of the nodes in each of the two partitions.

Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

Constraints:

• The number of nodes in the list is in the range [0, 200].
• -100 <= Node.val <= 100
• -200 <= x <= 200

SOLUTION:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def lessThan(self, head, x):
        if not head:
            return head
        if head.val >= x:
            return self.lessThan(head.next, x)
        newhead = TreeNode(val = head.val)
        newhead.next = self.lessThan(head.next, x)
        return newhead

    def greaterThan(self, head, x):
        if not head:
            return head
        if head.val < x:
            return self.greaterThan(head.next, x)
        newhead = TreeNode(val = head.val)
        newhead.next = self.greaterThan(head.next, x)
        return newhead

    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        left = self.lessThan(head, x)
        right = self.greaterThan(head, x)
        if not left:
            return right
        curr = left
        while curr and curr.next:
            curr = curr.next
        curr.next = right
        return left