Partitioning a Linked List based on a value

Why Partitioning: Separates elements by predicate—foundation for quicksort on linked lists, routing (high/low priority), and stream processing (route by key).

Two-Pointer Approach: Maintain two lists: less_than and ge_than. Single pass, O(n), O(1) extra (reuse nodes). Stable partition preserves relative order within each group.

Scalability: In-memory only—linked lists aren't used at big-data scale. Conceptually maps to: partitioning RDD/DataFrame by predicate, or routing events to high/low priority queues. For distributed sort: similar 'partition by range' logic in Spark.

def partition(head, x):
less = less_h = ListNode(0)
ge = ge_h = ListNode(0)
while head:
if head.val < x:
less.next = head; less = less.next
else:
ge.next = head; ge = ge.next
head = head.next
less.next = ge_h.next; ge.next = None
return less_h.next