Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Program:

ListNode *partition(ListNode *head, int x) {
ListNode *res = NULL;
ListNode *temp=head,*new_head=NULL;
while(temp)
{

if(temp->val < x)

{

if(!res)
{

res=new ListNode(temp->val);
temp=temp->next;
// cout << “val1<x”;
new_head=res;

}
else
{

while(res->next)

res=res->next;
res->next=new ListNode(temp->val);
temp=temp->next;

}

}
else
{

temp=temp->next;
// cout << “val1>x”;

}

}
temp=head;
// if(temp)
// cout << temp->val;
while(temp)
{
if(temp->val >=x)
{

if(!res)
{
res=new ListNode(temp->val);
temp=temp->next;
// cout << “val>x”;
new_head=res;
}
else
{
// cout << “val<x”;
while(res->next)
res=res->next;
res->next=new ListNode(temp->val);
temp=temp->next;
}

}

else
{

temp=temp->next;
// cout << “val<x”;

}

}

return new_head;
}

Runtime: 44  ms