Watch 10 video solutions for Partition List, a medium level problem involving Linked List, Two Pointers. This walkthrough by NeetCode has 38,506 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |