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的节点在大于或者等于x的节点的前面，而且必须保证这些节点在链表中的相对顺序。
这题可以这样简单的思考：找到第一个比3大于或者等于的，然后把该节点后面小于3的节点插入到它的前面。比如这里，找到4，后面是3，继续遍历，找到2，把2取下，插入到4前面，再往后是5，继续遍历，找到2，把2取下，插入到4前面。
想法是这样，但是在编写代码的时候要处理很多细节问题，比如，要取下小于x的节点，那么就要保存该节点的前面的节点的指针，必然要用两个指针进行遍历，另一方面，当第一个是大于或者等于x的节点和当第一个是小于x的节点的处理方式也不一样。
代码中设置了5个变量：
（1）ListNode *p 遍历的当前节点的前面的节点
（2）ListNode *q 遍历的当前节点
（3） ListNode *r 指向第一个大于或者等于x的节点
（4） bool set r是否指向了第一个大于或者等于x的节点
（5） bool first 是否是第一次遍历，因为第一次遍历的行为和后面额行为主要差别在于p节点是否移动。
因为有些情况实在不好进行合并，因此基本都进行了分类讨论。
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
ListNode *p = head, *q = head, *r = NULL;
bool set = false, first = true;
while(q) {
if(!first) {
if(q->val >= x && !set) {
r = p;
p = q;
q = q->next;
set = true;
}
else if(q->val < x && set) {
p->next = q->next;
if(r == head && r->val >= x) {
q->next = head;
head = q;
r = head;
}
else {
q->next = r->next;
r->next = q;
r = q;
}
q = p->next;
}
else {
p = q;
q = q->next;
}
}
else {
if(q->val >= x) {
r = q;
q = q->next;
set = true;
}
else
q = q->next;
first = false;
}
}
return head;
}
};