Partition List

Share

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.

Example 1
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.
Example 2
Input: head = [2,1], x = 2
Output: [1,2]

Solution Approach

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.

Java
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