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.
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
if(head == NULL || head->next == NULL) return head;
ListNode* p = new ListNode(), *pre_p = p;
ListNode *q = new ListNode(), *pre_q = q;
while(head){
if(head->val < x){
ListNode *tmp = head->next;
head->next = pre_p->next;
pre_p->next = head;
pre_p = pre_p->next;
head=tmp;
}else{
ListNode *tmp = head->next;
head->next = pre_q->next;
pre_q->next = head;
pre_q = pre_q->next;
head=tmp;
}
}
pre_p->next = q->next;
return p->next;
}
};