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 an integer x, rearrange the nodes so that all nodes with values less than x appear before nodes greater than or equal to x. The relative order of nodes in each partition must remain the same.
Approach 1: Two-Pointer Partition Lists (O(n) time, O(1) extra space)
This approach builds two temporary chains while traversing the list once. One list stores nodes with values < x, and the other stores nodes with values >= x. Use two pointers (usually dummy heads) to append nodes as you iterate through the original list. After processing all nodes, connect the end of the smaller list to the head of the larger list. The key insight is that you never create new nodes—you only rewire next pointers—so the relative order inside each partition stays intact. This technique is a classic application of linked list manipulation combined with the two pointers pattern.
Approach 2: In-Place Rearrangement (O(n) time, O(1) space)
Instead of maintaining two separate lists, this method reorganizes nodes directly inside the existing structure. Track the tail of the "less than x" region while scanning the list. When a node with value < x appears after larger elements, detach it and move it right after the partition boundary. Pointer updates must be handled carefully to avoid breaking the list. The advantage is strict constant extra space with no additional dummy lists. This version emphasizes pointer operations and deeper understanding of linked list structure.
Recommended for interviews: The two-pointer partition list method is what most interviewers expect. It is simple, safe, and easy to reason about while maintaining stable ordering. The in-place rearrangement approach demonstrates stronger pointer manipulation skills and can impress interviewers if implemented cleanly. Showing the straightforward partition first proves correctness; discussing the in-place optimization shows deeper mastery of two pointer and linked list techniques.
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.
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.
Time Complexity: O(n)
Space Complexity: O(1)
We create two linked lists l and r, one to store nodes less than x and the other to store nodes greater than or equal to x. Then we concatenate them.
The time complexity is O(n), where n is the length of the original linked list. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| 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) |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Partition Lists | O(n) | O(1) | Best general solution. Clean logic using two dummy heads and stable ordering. |
| In-Place Rearrangement | O(n) | O(1) | When minimizing auxiliary structures and demonstrating advanced pointer manipulation. |
Partition List - Linked List - Leetcode 86 • NeetCode • 45,462 views views
Watch 9 more video solutions →Practice Partition List with our built-in code editor and test cases.
Practice on FleetCode