# In-place solution c++

• The idea is, move the no smaller part as a group (sub-list).

1->3->1->4->1->1->5
||
------------------------
1->3->1->4->1->1->5
||
------------------------
1->3->1->4->1->1->5
|  |
------------------------
1->1->3->4->1->1->5
||
------------------------
1->1->3->4->1->1->5
|  |
------------------------
1->1->3->4->1->1->5
|     |
------------------------
1->1->1->3->4->1->5
|     |
------------------------
1->1->1->1->3->4->5
|     |

So, first swap 3 with 1, then 34 with 1, next swap 345 with something, ...
Code if needed:

ListNode* partition(ListNode* head, int x) {
ListNode* dummy= new ListNode(0);
ListNode *h=dummy,*t1,*t2;
while (h->next && h->next->val < x) h=h->next;
t1=h;t2=h->next;
while (t2){
while (t2 && t2->val >=x){
t1=t1->next;
t2=t2->next;
}
if (t2){
t1->next=t2->next;
t2->next=h->next;
h->next=t2;
h=h->next;
t2=t1->next;
}
}
return dummy->next;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.