```
ListNode* partition(ListNode* head, int x) {
ListNode* cur = new ListNode(0);
cur->next = head;
head = cur;
/*find insert position for elements that < x*/
while (cur->next && cur->next->val < x)
cur = cur->next;
ListNode* insPos = cur;
ListNode* tmp;
/*keep traversing list, insert lower val elements
after InsPos and skip >= x elements*/
while (cur->next) {
if (cur->next->val < x) {
tmp = cur->next;
cur->next = tmp->next;
tmp->next = insPos->next;
insPos->next = tmp;
insPos = insPos->next;
} else {
cur = cur->next;
}
}
return head->next;
}
```