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)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
if not head:
return None
less, gt_eq = None, None
left, right = None, None
node = head
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)