Partition List

Build two stable chains

Create dummy heads and tails for nodes smaller than x and nodes greater than or equal to x. Walk the original list once, saving next before rewiring if needed, then append the current node to the appropriate tail. At the end, set the large tail's next to null and connect the small tail to the first large node. Return the small dummy's next.

The invariant is that each auxiliary chain contains exactly the processed nodes of its class in original order. The explicit null termination prevents a stale original pointer from creating a cycle or dragging a small node after the large partition. Runtime is O(n) and extra space is O(1) aside from dummy nodes. Test empty list, all-small, all-large, alternating values, nodes equal to pivot, and one node. Do not allocate replacement data nodes unless the API requires immutability, and do not forget to preserve relative order: swapping values or unstable partitioning violates the usual contract.