Given the head of a linked list and a value x, partition it such that all nodes with value < x come before nodes with value >= x, preserving original relative order within each partition.

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Explanation: Nodes < 3: 1→2→2. Nodes ≥ 3: 4→3→5. Joined. Input: head = [2,1], x = 2
Output: [1,2]

Maintain two dummy-headed lists: one for nodes < x, one for nodes >= x. Traverse the original list, appending each node to the appropriate list. Finally connect the two lists.

public ListNode partition(ListNode head, int x) { ListNode lessHead = new ListNode(0), greaterHead = new ListNode(0); ListNode less = lessHead, 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; }
Complexity Analysis:

Time complexity: O(n)
Space complexity: O(1) — in-place rewiring