# 86 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:

``````1 -> 4 -> 3 -> 2 -> 5 -> 2
v
1 -> 2 -> 2 -> 4 -> 3 -> 5

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`
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 `````` ``````# 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]: # big_dummy_head -> (greater than or equal to x) # small_dummy_head -> (smaller than x .. -> small_last) big_dummy_head = ListNode(0, head) small_dummy_head = small_last = ListNode() prev, curr = big_dummy_head, head while curr: if curr.val < x: prev.next = curr.next small_last.next = curr small_last = small_last.next else: prev = curr curr = curr.next small_last.next = big_dummy_head.next return small_dummy_head.next``````