AlgoMaster Logo

Partition List

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

This problem asks for a stable partition of a linked list. We split the nodes into two groups based on a threshold value x: nodes with values less than x, and nodes with values greater than or equal to x. Within each group, the original order must be preserved.

The word "preserve" carries weight here. A rearrangement that puts every "less than 3" value before every "greater than or equal to 3" value is not enough on its own. For example, with [1, 4, 3, 2, 5, 2] and x = 3, the output [2, 2, 1, 3, 5, 4] satisfies the split but is wrong, because the values within each group no longer follow their original order. The relative order inside each group has to match the input.

This is partitioning, not sorting. Two nodes that are both less than x should appear in the same relative order they had in the original list. That requirement rules out any rearrangement that shuffles nodes within a group, so the approach has to be stable.

Key Constraints:

  • 0 <= n <= 200 -> The list can be empty, so the solution has to return correctly when head is null.
  • -100 <= Node.val <= 100 -> Values can be negative and can equal x. The split is strictly "less than," so a node whose value equals x belongs in the "greater than or equal to" group.
  • -200 <= x <= 200 -> Since x can fall below every value or above every value, one of the two groups may end up empty. The connection step has to stay correct when the "less" chain or the "greater" chain has no real nodes.

Approach 1: Collect into Array and Rebuild

Intuition

Traverse the linked list, collect each value into one of two arrays based on whether it is less than x, then build a fresh linked list from the two arrays concatenated in order.

This avoids pointer manipulation entirely. Arrays are easier to reason about than rewired next pointers, and appending to an array preserves the order values were seen, which gives us the stability the problem requires.

Algorithm

  1. Traverse the linked list and collect all values into an array.
  2. Create two arrays: one for values less than x, one for values greater than or equal to x.
  3. Concatenate the two arrays (less-than first, then greater-or-equal).
  4. Build a new linked list from the concatenated array and return it.

Example Walkthrough

Input:

1
4
3
2
5
2
null
head

After partitioning into two groups:

0
1
1
2
2
2
less
0
4
1
3
2
5
greater

Concatenate and rebuild:

1
2
2
4
3
5
null
result

Code

This is correct, but it allocates a whole new list. The next approach reuses the original nodes by rewiring their next pointers, dropping the extra memory to constant.

Approach 2: Two Dummy Lists (Optimal)

Intuition

Instead of copying values, rewire the existing nodes into two separate chains. One chain collects all nodes with values less than x, the other collects all nodes with values greater than or equal to x. Then connect the tail of the first chain to the head of the second.

Each chain starts with a dummy head node. Without it, the first node added to a chain would need special handling because there is no tail to append to yet. With a dummy, every chain begins with a non-null node, so the code can always append to tail.next and advance the tail, no empty-chain check required.

Algorithm

  1. Create two dummy nodes: lessHead and greaterHead. These will serve as the anchors for our two chains.
  2. Initialize two tail pointers: lessTail and greaterTail, both pointing to their respective dummy nodes.
  3. Traverse the original list. For each node:
    • If node.val < x, append it to the "less" chain.
    • Otherwise, append it to the "greater" chain.
  4. Connect the two chains: set lessTail.next = greaterHead.next (skip the dummy).
  5. Terminate the list: set greaterTail.next = null to avoid cycles.
  6. Return lessHead.next (skip the dummy).

Example Walkthrough

1Initialize: two dummy heads, current at node 1
1
current
4
3
2
5
2
null
1/6

Code