/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
auto leftDummyHead = new ListNode(), rightDummyHead = new ListNode();
auto leftTail = leftDummyHead, rightTail = rightDummyHead;
while (head) {
if (head->val < x) {
leftTail->next = head;
leftTail = leftTail->next;
} else {
rightTail->next = head;
rightTail = rightTail->next;
}
head = head->next;
}
leftTail->next = rightDummyHead->next;
rightTail->next = nullptr;
return leftDummyHead->next;
}
};