#86 Partition List

frequently reported atAmazon Microsoft

the problem

In plain words

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

in head = [1,4,3,2,5,2], x = 3

out [1,2,2,4,3,5]

in head = [2,1], x = 2

out [1,2]

0 ≤ number of nodes ≤ 200
-100 ≤ Node.val ≤ 100
-200 ≤ x ≤ 200

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternIn-place linked-list rewiring

Build two chains while walking — "less than x" and "the rest" — each behind its own dummy head. Appending at a tail keeps the order. Then join the chains and end the second one.

solutions

From brute force to optimal

Collect the small values and the rest in two ArrayLists, then build a brand-new list.

Walk once, adding each value to small or rest.
small.addAll(rest).
Build new nodes from the combined list.

timeO(n)

One pass to split, one to build.

spaceO(n)

Two value lists plus n new nodes.

javajava.util.*

1class Solution {2    public ListNode partition(ListNode head, int x) {3        List<Integer> small = new ArrayList<>(), rest = new ArrayList<>();4        for (ListNode p = head; p != null; p = p.next) (p.val < x ? small : rest).add(p.val);5        small.addAll(rest);                        // same relative order inside each group6        ListNode dummy = new ListNode();7        ListNode tail = dummy;8        for (int v : small) {                      // builds brand-new nodes9            tail.next = new ListNode(v);10            tail = tail.next;11        }12        return dummy.next;13    }14}

Append each node to the tail of the small or the big chain; then small's tail → big's first node; big's tail → null.

smallHead, bigHead = two dummies; small, big = their tails.
For each node: append it to small (val < x) or big (otherwise).
big.next = null; small.next = bigHead.next.
Return smallHead.next.

timeO(n)

One pass over the list.

spaceO(1)

Two dummies and two tails; the nodes are re-linked, not copied.

javajava.util.*

1class Solution {2    public ListNode partition(ListNode head, int x) {3        ListNode smallHead = new ListNode(), bigHead = new ListNode(); // two empty chains4        ListNode small = smallHead, big = bigHead;5        for (ListNode p = head; p != null; p = p.next) {6            if (p.val < x) {7                small.next = p;                    // re-link the node itself8                small = p;9            } else {10                big.next = p;11                big = p;12            }13        }14        big.next = null;                           // the last big node may still point into the old list15        small.next = bigHead.next;                 // small chain, then big chain16        return smallHead.next;17    }18}

in the room

How to say it in the interview

talk track

Point out that "keep relative order" means stable — so swapping values like quicksort's partition is out.
Two dummies mean no "is this chain still empty?" checks.
Say why big.next = null matters: the last big node may still point at a small node from the old list.

traps

Forgetting big.next = null → a cycle (the last big node still points into the old list).
Partitioning in place by swapping values (like Lomuto's partition) — not stable, so the order inside the groups breaks.

what they ask next

Follow-ups

Three groups (less, equal, greater)?

Three dummy-headed chains, joined in order — a stable three-way split, still O(n) time and O(1) space.

Quicksort on a linked list?

This partition is its core step: recurse on both chains and join them. But the worst case is O(n²); merge sort (Sort List, LC 148) is the usual choice for lists.

before you submit

Edge cases to test

Empty list → null.
All values < x, or all ≥ x → the order is unchanged.
Values equal to x go to the second group.
x doesn't appear in the list at all.

practise next