Partition List

Medium15–20 min

Topics

Linked ListTwo Pointers

Companies

AmazonMicrosoftFacebook

Given the head of a linked list and a value x, rearrange the nodes so every node with a value less than x comes before every node with a value of x or more — preserving each group's original relative order — and return the new head. No node's value changes, and the split doesn't need to place x itself in any particular spot beyond "not less than x". Growing two separate chains while walking the list once handles this directly: every node gets appended to whichever chain it belongs in, becoming that chain's new tail. A dummy node anchoring each chain means the very first node appended works exactly the same way as every later one — no special case for "is this the first node in this group?" Once every node has been placed, joining the less chain's tail to the geq chain's head produces the final list in one splice.

Test Case 1:

Input:head = [5, 9, 2, 8, 1, 6], x = 5

Output:[2, 1, 5, 9, 8, 6]

Explanation:Every value less than 5 (2, 1) comes first in original order, then every value 5 or more (5, 9, 8, 6) follows in original order.

Test Case 2:

Input:head = [3, 1], x = 2

Output:[1, 3]

Explanation:1 is less than 2 and moves first; 3 stays in the second group.

Test Case 3:

Input:head = [4], x = 4

Output:[4]

Explanation:4 is not less than the pivot (ties go with the second group), so a single node stays exactly where it is.

Constraints

◆0 ≤ number of nodes in head ≤ 200
◆-1000 ≤ node value, x ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Collect into Two Lists, Then Write Back

Good

Walk the list once, sorting every value into one of two arrays based on whether it's less than x or not. Concatenate the less-than values before the rest, then walk the list a second time, overwriting each node's value in that new order. Correct, but the two arrays cost O(n) extra space where the optimal solution needs none.

TimeO(n)

SpaceO(n)

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

class Solution {
    public Node partition(Node head, int x) {
        List<Integer> less = new ArrayList<>();
        List<Integer> geq = new ArrayList<>();
        Node curr = head;
        while (curr != null) {
            if (curr.val < x) {
                less.add(curr.val);
            } else {
                geq.add(curr.val);
            }
            curr = curr.next;
        }
        List<Integer> combined = new ArrayList<>(less);
        combined.addAll(geq);
        curr = head;
        for (int v : combined) {
            curr.val = v;
            curr = curr.next;
        }
        return head;
    }
}

Optimal — Build Two Chains with Dummy Heads

Optimal

Grow two separate chains while walking the list once: a "less" chain and a "greater-or-equal" chain, each anchored by its own dummy head so the very first real node appended works the same way as every later one. Every visited node gets appended to whichever chain it belongs in and becomes that chain's new tail — no values are copied, the existing nodes are simply relinked. Once every node has been placed, the less chain's tail is pointed at the geq chain's head, the geq chain's tail is terminated with null, and the less chain's dummy-following node is the new head.