86. Partition List
1. Description
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.
2. Example
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]
3. Constraints
- The number of nodes in the list is in the range [0, 200].
- -100 <= Node.val <= 100
- -200 <= x <= 200
4. Solutions
Two Pointers
n is the number of nodes in head
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode less_dummy, greater_equal_dummy;
ListNode *less_tail = &less_dummy, *greater_equal_tail = &greater_equal_dummy;
while (head != nullptr) {
if (head->val < x) {
less_tail->next = head;
less_tail = less_tail->next;
} else {
greater_equal_tail->next = head;
greater_equal_tail = greater_equal_tail->next;
}
head = head->next;
}
less_tail->next = greater_equal_dummy.next;
greater_equal_tail->next = nullptr;
return less_dummy.next;
}
};