Leetcode: Partition List
Partition a linked list given a value x as a pivot element so that all nodes that are
smaller than x come before all nodes that are greater or equal than x. The original
order of the elements should be retained.
This can be solved by creating two sub lists with empty nodes, called left and right
and then concatenating those lists in the last step. The easiest way to achieve this is
to create two new empty nodes and then, return left.next. This avoids having to keep
track of None inside the loop and simpliefies the code.
# 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]:
if head is None or head.next is None:
return head
left_head = ListNode()
right_head = ListNode()
left_curr = left_head
right_curr = right_head
curr = head
while curr is not None:
if curr.val < x:
left_curr.next = curr
left_curr = left_curr.next
else:
right_curr.next = curr
right_curr = right_curr.next
curr = curr.next
left_curr.next = right_head.next
right_curr.next = None
return left_head.next