## Description

Given 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:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5


## Solutions

### 1. Direct

# Time: O(n)
# Space: O(1)
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
return None
less, gt_eq = None, None
left, right = None, None
while node:
if node.val < x:
if not less:
left = node
else:
less.next = node
less = node
else: # node.val >= x
if not gt_eq:
right = node
else:
gt_eq.next = node
gt_eq = node
node = node.next
if not less or not gt_eq:
return right or left
else:
less.next = right
gt_eq.next = None
return left
# 166/166 cases passed (28 ms)
# Your runtime beats 94.34 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.6 MB)