【初阶数据结构】——牛客：CM11 链表分割
1. 题目介绍
链接: link
这道题是给我们一个链表和一个值X ，要求我们以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。 最终返回重新排列之后的链表的头指针。
2. 思路分析
那这道题呢比较简单的一种思路是这样的：
新建两个链表less和greater，遍历原链表将原链表中值小于X的结点尾插（题目要求不能改变原来的数据顺序）到less链表，将大于等于X的结点尾插到greater链表，然后将两个链表合并：greater链接到less后面。
那么另外呢：
对于新建的链表我们可以选择不带哨兵位的头结点，也可以选择带哨兵位的头结点的链表。 但是，对于这道题来说建议大家选取带头结点的链表结构。 如果不带头的话，实现起来就会比较麻烦。带头的和就会方便很多。 首先带头结点的话尾插的时候空表的情况不需要单独判断，另外如果出现链表结点的值都比给定的X大，那这样第一个链表就是空，如果有头结点的话，空表状态也有一个头结点，这里把第二个链表往第一个链表后面链接的时候也会很方便。 当然如果是带头结点的话最后链接返回之后最好把头结点也释放掉。
那按照上面的思路，我们来尝试写一下代码
3. 代码实现
感觉好像没什么问题了，我们来提交一下：
?，我们看到没有通过全部的测试用例，怎么回事呢？
有一种情况我们没能处理好： 如果重新排列之后的尾结点不是原链表的尾结点，就会有一个问题。 其实我们上面给大家画的那个图就是这样
大家看到了嘛，这里的7这个结点，是重新排列之后的尾结点，但是不是原链表的尾结点，我们这样连接之后，7是尾结点，尾结点的next应该指向空，但是此时它仍然指向原链表中他后面的那个结点4，那么这样的话我们返回的链表就是一个带环的链表，遍历的时候就会陷入死循环。
我们可以来测试一下图中的这个测试用例，看看是不是这样：
我们看到后面就陷入了7，4，2，6的死循环。
所以：
不论最终的尾结点是不是原链表的尾结点，我们都把它置成NULL
再来提交
就?了。
class Partition {
public:
struct ListNode* partition(struct ListNode* pHead, int x) {
struct ListNode* smallhead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* bighead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* smalltail = smallhead;
smalltail->next = NULL;
struct ListNode* bigtail = bighead;
bigtail->next = NULL;
struct ListNode* cur = pHead;
while (cur) {
if (cur->val < x) {
smalltail->next = cur;
smalltail = cur;
} else {
bigtail->next = cur;
bigtail = cur;
}
cur = cur->next;
}
smalltail->next = bighead->next;
bigtail->next=NULL;
pHead = smallhead->next;
free(smallhead);
free(bighead);
return pHead;
}
};