Partition List is a linked list problem that tests whether you can reorganize nodes while preserving their relative order. You are given the head of a singly linked list and a value x. Your task is to rearrange the list so that all nodes with values less than x come before nodes with values greater than or equal to x.
The important constraint is stability. You are not allowed to change the relative order of nodes within each group. In other words, nodes less than x must appear in the same order they originally appeared, and the same rule applies to nodes greater than or equal to x.
This problem often looks simpler than it actually is. Many candidates try to swap node values or reorder nodes in place and accidentally break the ordering requirement. Interviewers use this problem to see if you can manipulate linked lists cleanly without losing track of pointers.
Why direct in-place swapping causes issues
If this were an array, partitioning would be straightforward. But in a linked list, you do not have random access. Once you start swapping nodes around, it becomes easy to lose references or reverse parts of the list unintentionally.
Another common mistake is to collect values into two arrays and rebuild the list. While that can work, it uses extra memory and misses the opportunity to show clean pointer manipulation, which is often the real point of the question.
The best solution keeps everything in a single pass and uses only a few extra pointers.
The key idea behind the solution
The simplest and most reliable approach is to split the list into two separate lists as you traverse it.
One list will hold all nodes with values less than x.
The other list will hold all nodes with values greater than or equal to x.
As you scan the original list from left to right, you append each node to the appropriate list. Because you append in the order you encounter nodes, the original relative order is preserved automatically.
Once you finish traversing the list, you connect the two lists together.
Want to explore more coding problem solutions? Check out the Different Ways to Add Parentheses and Online Stock Span coding problem solutions.
How the logic works step by step
You start by creating two dummy nodes. One represents the head of the “less than x” list, and the other represents the head of the “greater than or equal to x” list.
You also maintain two pointers that move along these lists as you add nodes.
Now you walk through the original list one node at a time.
If the current node’s value is less than x, you attach it to the end of the first list and move that pointer forward.
If the value is greater than or equal to x, you attach it to the end of the second list and move that pointer forward.
You do not create new nodes. You reuse the existing ones by adjusting next pointers.
After the traversal is complete, you connect the end of the “less than” list to the beginning of the “greater than or equal to” list.
Finally, you make sure the last node of the second list points to null to avoid accidental cycles.
The new head of the partitioned list is the node following the first dummy node.
Why this approach works so well
This method works because it separates concerns cleanly.
You never need to move nodes backward or search for insertion points. Each node is handled exactly once, and its position relative to similar nodes is preserved.
Using dummy nodes simplifies edge cases. Whether the first node belongs to the left or right partition, the logic remains the same.
This clarity is something interviewers value highly.
Performance in simple terms
The list is traversed once, so the time complexity is linear. Only a few extra pointers are used, so space usage is constant.
This is optimal for a linked list partitioning problem.
Top comments (0)