Partition List

Intuition

Trying to shuffle nodes within a single list quickly becomes error-prone. It is far cleaner to split the traversal into two independent output chains: one collecting nodes below x and one collecting nodes at or above x. Because we append nodes in the order we encounter them, each chain automatically preserves the original relative order for its group. Two dummy heads make appending trivial, since each chain always has a stable tail to hang the next node on. Once the scan is done, we join the tail of the smaller chain to the head of the larger chain and terminate the list.

Algorithm walkthrough

1. 1Create two dummy heads, lessDummy and greaterDummy, with tails lessTail and greaterTail pointing at them.
2. 2Walk the original list one node at a time.
3. 3If the current node's value is less than x, append it to lessTail; otherwise append it to greaterTail, then advance that tail.
4. 4After the walk, terminate the greater chain by setting greaterTail.next to null.
5. 5Link the two chains by setting lessTail.next to greaterDummy.next.
6. 6Return lessDummy.next as the head of the partitioned list.

Implementation

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        less_dummy = ListNode(0)
        greater_dummy = ListNode(0)
        less_tail = less_dummy
        greater_tail = greater_dummy
        current = head
        while current:
            if current.val < x:
                less_tail.next = current
                less_tail = less_tail.next
            else:
                greater_tail.next = current
                greater_tail = greater_tail.next
            current = current.next
        greater_tail.next = None
        less_tail.next = greater_dummy.next
        return less_dummy.next