```
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* left = nullptr;
ListNode* right = head;
while (right && right->val < x) {
left = right;
right = right->next;
}
if (!right)
return head;
for (ListNode* p = right; p->next; ) {
if (p->next->val < x) {
if (left == nullptr) {
head = left = p->next;
} else {
left->next = p->next;
left = p->next;
}
p->next = p->next->next;
left->next = right;
} else {
p = p->next;
}
}
return head;
}
};
```