```
/*
* find the first element >= 'x',
* the element after it whose val < x will insert before the first elemt >= 'x'
* O(n)
*/
class Solution {
public: // tail insert x times ,each time inset smallest
ListNode* partition(ListNode* head, int x) {
ListNode *pre_p = NULL, * p =head;
while(p != NULL){ // find first >= 'x' pivot
if(p -> val >= x)break;
else {pre_p = p; p = p-> next;}
}
if(p == NULL)return head;//not find ,it means all the element < x
ListNode *pre = p,*cur = p -> next;
while(cur != NULL){ // traverse to cope with the elements after the pivot
if(cur-> val < x){
pre -> next =cur -> next;
if(pre_p == NULL){head= cur;cur -> next = p;}
// if the head`s vale > x, the head is pivot
else{
cur -> next =pre_p -> next;
pre_p -> next = cur;
}
pre_p = cur;
cur = pre -> next;
}
else {pre = cur; cur = cur -> next;}
}
return head;
}
};
```