Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example 1:
Input: head = [1,4,3,2,5,2], x = 3 Output: [1,2,2,4,3,5]
Example 2:
Input: head = [2,1], x = 2 Output: [1,2]
Constraints:
[0, 200].-100 <= Node.val <= 100-200 <= x <= 200Problem Overview: Given the head of a linked list and a value x, reorder the list so that all nodes with values less than x come before nodes with values greater than or equal to x. The relative order of nodes in each partition must remain the same. The task is essentially a stable partition operation applied to a linked list.
Approach 1: Two-Pointer Approach (O(n) time, O(1) space)
This approach builds two separate linked lists during a single pass. Use two dummy heads: one for nodes < x and another for nodes >= x. Traverse the original list once, and for each node append it to the appropriate list using tail pointers. After the traversal finishes, connect the tail of the smaller list to the head of the greater-or-equal list. Because nodes are appended in traversal order, the relative ordering is preserved automatically. This technique relies on pointer manipulation common in two pointer style linked list problems where separate tails track list growth.
The key insight is avoiding expensive insertions or array conversions. Each node is visited exactly once, and pointer rewiring handles the partitioning. Time complexity is O(n) because you iterate through the list once. Space complexity is O(1) since only a few pointers are used and no additional data structures proportional to input size are allocated. This is the most common and interview-friendly solution.
Approach 2: In-Place Rearrangement (O(n) time, O(1) space)
This method performs the partition directly within the existing list without building two explicit lists. Maintain a pointer marking the end of the "less-than-x" region. Traverse the list using a current pointer. When a node with value < x appears after nodes that are >= x, detach that node and insert it after the partition pointer. Then advance the partition pointer. Careful pointer updates ensure the remaining list stays connected during the move.
The benefit is that the algorithm truly rearranges nodes in-place while maintaining stability. No dummy lists are required, but pointer handling becomes slightly more complex because you must track the previous node during traversal and reconnect links correctly. Time complexity remains O(n) since each node is processed once, and space complexity is O(1) because only pointer references are used.
Recommended for interviews: The two-pointer partition approach is what most interviewers expect. It is easy to reason about, clearly preserves order, and avoids tricky pointer edge cases. Implementing the in-place rearrangement shows deeper comfort with linked list manipulation, but it is more error-prone under interview pressure. Demonstrating the two-list partition first and mentioning the in-place alternative shows strong problem-solving range.
This approach involves using two separate linked lists to store nodes that are less than x and nodes that are greater than or equal to x. You traverse the original list and attach each node to the appropriate list. Finally, you connect the two lists together to form the partitioned list.
This C implementation uses two dummy node pointers to build the 'less than x' and 'greater or equal to x' lists. It iterates through the original list only once, making the approach efficient.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the list.
Space Complexity: O(1), as we only use a constant amount of extra space.
This in-place rearrangement technique modifies the original list without the need of additional dummy nodes. This is accomplished by managing pointers to redefine segment connections efficiently.
This C implementation uses four pointers to represent the start and end of the 'before' and 'after' lists. As we traverse the original list, we reattach nodes to these lists, eventually connecting them at the end.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Two-Pointer Approach | Time Complexity: O(n), where n is the number of nodes in the list. |
| In-Place Rearrangement Approach | Time Complexity: O(n) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Partition Lists | O(n) | O(1) | Best general solution. Clean logic using two dummy lists and stable ordering. |
| In-Place Rearrangement | O(n) | O(1) | When you want to avoid building temporary lists and practice advanced pointer manipulation. |
Partition List - Linked List - Leetcode 86 • NeetCode • 38,506 views views
Watch 9 more video solutions →Practice Partition List with our built-in code editor and test cases.
Practice on FleetCode