82. Partition List

Build two chains in a single pass — one for nodes less than x, one for the rest — appending each node to the correct chain in order. Then stitch the 'less' chain in front of the 'greater-or-equal' chain.

Idea

We want all nodes < x before all nodes >= x, keeping each group's original order. Rather than swap nodes around, thread each node onto one of two separate lists as we scan: a less list and a greater list. Appending in scan order automatically preserves relative order. Finally, connect the tail of less to the head of greater.

Two dummy heads make appending clean and avoid empty-list special cases.

Algorithm

1. Create dummies: less_head -> less, greater_head -> greater.
2. For each node while scanning head:
   • If node.val < x: append to the less chain.
   • Else: append to the greater chain.
3. Terminate the greater chain: greater.next = None.
4. Join: less.next = greater_head.next.
5. Return less_head.next.

Worked example: list 1→4→3→2→5→2, x = 3

• less gets 1, 2, 2 (values < 3, in order); greater gets 4, 3, 5.
• Join: 1→2→2 then 4→3→5.

Result: 1→2→2→4→3→5.

Complexity

• Time: O(n) — one pass.
• Space: O(1) — only rewiring existing nodes.

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode lessHead = new ListNode(0);
        ListNode less = lessHead;
        ListNode greaterHead = new ListNode(0);
        ListNode greater = greaterHead;
        while (head != null) {
            if (head.val < x) {
                less.next = head;
                less = less.next;
            } else {
                greater.next = head;
                greater = greater.next;
            }
            head = head.next;
        }
        greater.next = null;
        less.next = greaterHead.next;
        return lessHead.next;
    }
}