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 singlylinked 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
