Partition List
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.
分析： 保持两个表头, 一个存大于等于 x 的结点，一个存小于 x 的结点。
注意：记住两个表尾，中间不能将其 next 指针设置为空。最后将存小值的表尾链接在另一个前面，两一个表尾 next 置为 NULL.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode *head1, *head2, *tail1, *tail2;
head1 = head2 = tail1 = tail2 = NULL;
while(head) {
if(head->val >= x) {
if(head2 == NULL) head2 = tail2 = head;
else { tail2->next = head; tail2 = tail2->next; }
} else {
if(head1 == NULL) head1 = tail1 = head;
else { tail1->next = head; tail1 = tail1->next; }
}
head = head->next;
}
if(head2) tail2->next = NULL;
if(head1) tail1->next = head2;
else head1 = head2;
return head1;
}
};