Partition Around Value
Problem
Given the head of a singly linked list and a pivot value, rearrange the nodes so every node holding a value below the pivot comes before every node holding a value at or above it. Inside each of the two groups the nodes keep the order they had originally. The pivot itself need not appear in the list.
Examples
Input: head = 1 -> 4 -> 3 -> 2 -> 5 -> 2, pivot = 3
Output: 1 -> 2 -> 2 -> 4 -> 3 -> 5
Why: both groups keep their original internal orderInput: head = 2 -> 1, pivot = 2
Output: 1 -> 2
Why: a node equal to the pivot belongs to the upper groupInput: head = empty, pivot = 0
Output: empty
Why: edge case, there is nothing to partitionHints
0 / 3
Swapping values around inside one list makes keeping the original order inside each group very hard. Think about the nodes as belonging to two separate streams instead.
Build the two groups as two chains while you walk the original list once, then join them. Appending to the end of a chain is what preserves the original order.
Keep a tail pointer for a low chain and a high chain, each behind a throwaway starter node. Send every node to whichever chain it belongs to. At the end, terminate the high chain, link the low chain to the start of the high chain, and return the first real low node.
Solution
Two chains are grown side by side during one walk of the original list, each appending at its tail so the original relative order survives inside both groups. Throwaway starter nodes remove the empty-chain special cases, and the join at the end is two pointer writes. The high chain must be terminated explicitly, because its last node still carries whatever link it had in the original list and would otherwise loop back. Time is O(n) and space is O(1), since only links change.
class Node:
def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def build(v): return Node(v[0], build(v[1:])) if v else None # list -> chain
def dump(h): return [h.val] + dump(h.next) if h else [] # chain -> list
def partition_around(head, pivot):
low = low_tail = Node(0) # values below the pivot, in original order
high = high_tail = Node(0) # values at or above the pivot
while head:
if head.val < pivot: low_tail.next, low_tail = head, head
else: high_tail.next, high_tail = head, head
head = head.next
high_tail.next = None # the old tail still points into the past
low_tail.next = high.next # stitch the two chains together
return low.next
print(dump(partition_around(build([1, 4, 3, 2, 5, 2]), 3))) # -> [1, 2, 2, 4, 3, 5]
print(dump(partition_around(build([2, 1]), 2))) # -> [1, 2]
print(dump(partition_around(build([]), 0))) # -> []Stuck on the idea rather than the code? Traversal and Search covers it.