题目
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，要求对链表结点按照以下要求重排：
（1）值小于x的结点，按照其原顺序排列与链表头部
（3）其余值不小于x的结点，按照其原顺序链接与尾部
AC代码
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if (!head || !head->next)
return head;
ListNode *p = head;
head = NULL;
ListNode *r = head;
//(1)寻找第一个不小于目标值的节点p，前n个小于x的节点逐个连接到head，保存尾结点r
while (p && p->val < x)
{
if (!head)
{
head = p;
r = head;
}
else{
r->next = p;
//保存新链表尾结点
r = r->next;
}
p = p->next;
r->next = NULL;
}//while
//如果此时p为空，已经没有其余节点，返回新链表head
if (!p)
return head;
//（2）p节点大于x，从下一个结点开始遍历，将小于x的结点连接到head中，原链表删除该结点
ListNode *pre = p , *q = p->next;
while (q)
{
if (q->val < x)
{
if (!head)
{
head = q;
r = head;
}
else{
r->next = q;
//保存新链表尾结点
r = r->next;
}
pre->next = q->next;
q = q->next;
r->next = NULL;
}//if
else{
pre = q;
q = q->next;
}//else
}//while
//如果此时，原链表还剩余结点，直接连接到r后面即可
if (p)
{
if (!head)
return p;
else
r->next = p;
}
return head;
}
};