C++ 6ms, simple solution

• ``````/*
The main idea is to find the node that hass less value than x, and move the small node before the large nodes.
use two pointers to indicate the begin of large group and the end of large group;
for example in a list
1->4->3->2->5->2 and x = 3
pt1 will point to 1, i.e. right before the large group (i.e., 4->3)
pt2 will point to 3
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode dummy(x-1); // use a smalller value to ensure this dummy node is in the small group
ListNode *pt=head, *pt1 = &dummy, *pt2=0;

while(pt){
if(pt->val < x){
//move the new small node point if pt2 has been assigned (ie. larger node has been found)
if (pt2){
pt2->next=pt->next;
pt->next=pt1->next;
pt1->next=pt;
}
//reasign pt1, the nearest smaller one before the big group
pt1=pt;
pt= (pt2) ? pt2->next : pt->next;
}
else {
pt2=pt;
pt=pt->next;
}
}
return dummy.next;
}
};

``````

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