一、描述
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
二、解析
新建两个哨兵指针
ListNode* phead2 = (ListNode*)malloc(sizeof(ListNode));
ListNode* phead3 = (ListNode*)malloc(sizeof(ListNode));
将大于val的节点放在phead3，小于val的节点连接到phead2中。
三、代码
ListNode* partition(ListNode* pHead, int x) {
// write code here
ListNode* cur = pHead;
ListNode* phead2 = (ListNode*)malloc(sizeof(ListNode));
ListNode* phead3 = (ListNode*)malloc(sizeof(ListNode));
ListNode* tail2 = phead2;
ListNode* tail3 = phead3;
//让tail 与 phead 开始时均指向哨兵位
if(cur == NULL)
return pHead;
while(cur)
{
if(cur->val < x)
{
tail2->next = cur;
tail2 = tail2->next;
}
else
{
tail3->next = cur;
tail3 = tail3->next;
}
cur = cur->next;
}
tail3->next = NULL; //防止环状列表的出现！
// tail2最终为phead2引领链表的尾部元素（不是空！）
tail2->next = phead3->next; //phead3是哨兵位，不会为空！
pHead = phead2->next;
free(phead2);
free(phead3);
return pHead;
}四、代码解析
1.
ListNode* phead2 = (ListNode*)malloc(sizeof(ListNode));
ListNode* phead3 = (ListNode*)malloc(sizeof(ListNode));
ListNode* tail2 = phead2;
ListNode* tail3 = phead3;
最开始，让tail与新的phead都从哨兵位开始.
2.
if(cur->val < x)
{
tail2->next = cur;
tail2 = tail2->next;
}
else
{
tail3->next = cur;
tail3 = tail3->next;
}
cur = cur->next;
将满足条件的节点分别分配到新节点
3.
tail3->next = NULL; //防止环状列表的出现！
被链接的链表尾部的next需要置空，放置出现环状列表！
4.
free(phead2);
free(phead3);
return pHead;
释放空间、返回指针
五、注意
单链表拆分成双链表时，一定要加上一步
tail3->next = NULL
放置出现环状链表。（否则内存超出限制）
