Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if(!head || !head->next)
return head;
ListNode *part2,*p1,*p2,*cur;
//if head is need to be updated
if(head->val >=x)
{
part2=head;
p2=head;
while(p2->next && p2->next->val >= x)
{
p2=p2->next;
}
if(!p2->next)
{
return head;
}
head=p2->next;
p1=head;
cur=p1;
}
//find head for partition 2
else
{
p1=head;
while(p1->next && p1->next->val < x)
{
p1=p1->next;
}
if(!p1->next)
{
return head;
}
part2=p1->next;
p2=part2;
cur=p2;
}
// bring nodes in order
cur=cur->next;
while(cur)
{
if(cur->val<x)
{
p1->next=cur;
p1=p1->next;
}
else
{
p2->next=cur;
p2=p2->next;
}
cur=cur->next;
}
//merge two partitions
p1->next=part2;
p2->next=NULL;
return head;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment