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 <= 200The key idea in Partition List is to rearrange nodes in a linked list so that all nodes with values less than a given pivot x appear before nodes greater than or equal to x, while preserving the original relative order.
A common and efficient strategy is to use two dummy linked lists. Traverse the original list once using a pointer. If the current node value is less than x, attach it to a smaller list; otherwise attach it to a greater-or-equal list. This technique avoids complex node swapping and maintains stable ordering.
After processing all nodes, simply connect the tail of the smaller list to the head of the greater-or-equal list. Using dummy nodes simplifies edge cases such as empty partitions and head replacements.
This approach requires only a single traversal of the list, giving O(n) time complexity and O(1) extra space since nodes are reused rather than copied.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Dummy Lists (Stable Partition) | O(n) | O(1) |
NeetCode
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.
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.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int x) { val = x; }
5}
6
7public class Solution {
8 public ListNode Partition(ListNode head, int x) {
9 ListNode lessHead = new ListNode(0);
10 ListNode greaterHead = new ListNode(0);
11 ListNode less = lessHead, greater = greaterHead;
12
13 while (head != null) {
14 if (head.val < x) {
less.next = head;
less = less.next;
} else {
greater.next = head;
greater = greater.next;
}
head = head.next;
}
greater.next = null;
less.next = greaterHead.next;
return lessHead.next;
}
}In this C# solution, similar dummy nodes are used to help construct two separate lists easily. The greater list is attached to the end of the less list to form the final partitioned list.
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.
Time Complexity: O(n)
Space Complexity: O(1)
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of linked list partitioning problems appear in FAANG and other top tech interviews. They test pointer manipulation, linked list traversal, and the ability to maintain stable ordering efficiently.
The optimal approach is to create two temporary linked lists: one for nodes less than x and another for nodes greater than or equal to x. Traverse the list once and append nodes accordingly, then connect the two lists. This preserves order and runs in O(n) time with O(1) extra space.
Dummy nodes act as stable starting points for new lists, making it easier to append nodes without special checks for empty lists. They simplify code and reduce the risk of pointer errors during list reconstruction.
A singly linked list with two pointer references or dummy head nodes works best. Dummy nodes simplify edge cases and allow you to append nodes to two partitions without complicated pointer manipulation.
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.