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;
    }
};