前言：
再来几天的题目，咱们进军二叉树
一、 题目：
现有一链表的头指针head，编写一段代码将所有的小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针
思路1：
假如可以不需要按原来顺序进行分割的话，那就是比大小然后进行头插和尾插就行了
思路2：
考虑到要按照原来数据的顺序，所以我们可以使用两个不同的链表来进行分别存放数据，一个存大于x的一个存小于x的，此时就可以实现链表的分割了
代码：
struct ListNode* partition(struct ListNode* phead, int x) { struct ListNode* lessHead = NULL; struct ListNode* lessTail = NULL; struct ListNode* greaterHead = NULL; struct ListNode* greaterTail = NULL; //开哨兵位的头结点，方便尾插 lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode)); lessTail->next = NULL; greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode)); greaterTail->next = NULL; struct ListNode* cur = phead;//此时虽然可以用phead去迭代，但是不好，所以我们都是找一个替死鬼去走 while (cur != NULL)//遍历 { if (cur->data < x)//判断 { //有了哨兵位，这边我们就可以直接进行链接，不需要判断头结点是否为空了 lessTail->next = cur; lessTail = cur; } else { greaterTail->next = cur; greaterHead = cur; } cur = cur->next; } //遍历完之后就完成了我需要的步骤，此时就是把这两个链表给链接在一起，这样就可以完成任务了 lessTail->next = greaterHead->next; greaterTail->next = NULL;//假如没有这句就会导致死循环（因为会头尾相连），关键所在，漏了就不好找了（叫我自己写，完……） struct LisNode* newHead = lessHead->next; free(lessHead); free(greaterHead); return newHead; }
