Watch 10 video solutions for Partition List, a medium level problem involving Linked List, Two Pointers. This walkthrough by NeetCode has 45,462 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 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.
| 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. |