Partition List

MediumLinked List · Dummy Heads · Two Chains🧩 Linked List Techniques LeetCode #86 ↗Updated Oct 30, 2026

Problem

Given the head of a linked list and a pivot value x, rearrange it so every node with value less than x comes before every node with value greater than or equal to x. Inside each group the nodes must keep their original relative order. Return the new head.

Inputhead = [1,4,3,2,5,2], x = 3Output[1,2,2,4,3,5]

Inputhead = [2,1], x = 2Output[1,2]

0 ≤ n ≤ 200 · -100 ≤ Node.val ≤ 100 · -200 ≤ x ≤ 200

Try it yourself

Java

class Solution {
    public ListNode partition(ListNode head, int x) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

This is a stable split, not a sort. Walk once and append each node to one of two growing chains (“small” and “big”), each started by a dummy node; then glue small's tail to big's head.

PatternLinked List Techniques

Instinct Nodes joined by next pointers and the task is to reverse, splice, merge, reorder or remove in place - grab a dummy head and rewire pointers carefully.

Memory hack Save next, flip, step - never let go of a rope before you've grabbed the next one.

Open the Linked List Techniques guide →

Approaches

Brute ForceCollect Values, Write Them Back

Time O(n)Space O(n)

Read the values into two lists — those below x and the rest — in the order they appear, which keeps each group stable. Concatenate the two lists and overwrite the node values from the head onwards.

Java

public ListNode partition(ListNode head, int x) {
    List<Integer> small = new ArrayList<>(), big = new ArrayList<>();
    for (ListNode c = head; c != null; c = c.next) {
        if (c.val < x) small.add(c.val);
        else big.add(c.val);
    }
    small.addAll(big); // final order of values
    ListNode c = head;
    for (int v : small) {
        c.val = v;
        c = c.next;
    }
    return head;
}

Correct and easy, but uses O(n) extra memory and rewrites values instead of relinking.

OptimalTwo Dummy-Headed Chains

Time O(n)Space O(1)

Keep two dummy nodes with moving tails. Each node is detached from its old position simply by being appended to the matching chain, so order inside each chain stays the original order. At the end, cut the big chain with null and link the small tail to the big head.

Java

public ListNode partition(ListNode head, int x) {
    ListNode smallDummy = new ListNode(0), bigDummy = new ListNode(0);
    ListNode small = smallDummy, big = bigDummy;
    for (ListNode c = head; c != null; c = c.next) {
        if (c.val < x) {
            small.next = c;
            small = c;
        } else {
            big.next = c;
            big = c;
        }
    }
    big.next = null;              // last big node may still point into small chain
    small.next = bigDummy.next;   // glue the two chains
    return smallDummy.next;
}

Single pass, constant extra memory, and moves real nodes — the expected answer.

Pro tip

Say out loud why big.next = null is required — without it the list can end in a cycle.

At a glance

Level	Approach	Time	Space
Brute Force	Collect Values, Write Them Back	`O(n)`	`O(n)`
Optimal	Two Dummy-Headed Chains	`O(n)`	`O(1)`

Common pitfalls

Forgetting big.next = null — the old link can create a cycle.
Treating it as a sort — values within a group must not be reordered.
Putting nodes equal to x into the small group; only strictly smaller ones go first.

Interview tips

Clarify stability up front: relative order inside each group is preserved.
Dummy heads remove all special cases for an empty group or empty list.
Trace [1,4,3,2,5,2], x=3 to show the two chains being built.

Pattern

Two dummy-headed chains → stably split a linked list by a predicate (odd/even, < x) in one pass.

My notes saved in this browser