Partition List

The key idea

Build two separate lists in a single pass — one for nodes strictly less than x and one for nodes greater than or equal to x — appending each node to the tail of its group. Because you always append, the original relative order inside each group is preserved. Finally splice the less-than list in front of the greater-or-equal list.

Problem

Given the head of a linked list and a value x, partition it so that all nodes less than x come before the nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Constraints

The number of nodes in the list is in the range [0, 200].
-100 <= Node.val <= 100
-200 <= x <= 200

Examples

Input: head = [1,4,3,2,5,2], x = 3 Output: [1,2,2,4,3,5]

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

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →