1. 题目分析

现有一链表的头指针 ListNode* pHead，给一定值 x；

编写一段代码将所有小于 x 的结点排在其余结点之前，且不能改变原来的数据顺序；

返回重新排列后的链表的头指针。

示例一

输入：[3，5，1，6，3，4]，x = 4

输出：[3，1，3，5，6，4]。

注意：x 等于 4，那么比 x 小的就是：3，1，3，所以这三个数要排在前面，顺序不能变；

那么比 x 大的就是：5，6，所以这两个数要排在 3，1，3 的后面，顺序不能变；

再把 x 放在最后

2. 题目图解

这道题的解题思路为：

（1）遍历原链表；

（2）把 小于 x 的插入到一个新的链表 1；

（3）把 大于等于 x 的插入到一个新的链表 2；

（4）然后把 链表 1 和 链表 2 链接起来；

定义 cur 指向原链表的头节点，用来遍历原链表；

定义 链表 1，lessHead 和 lessTail 都指向 哨兵位 的节点（不为 NULL）；

定义 链表 2，greaterHead 和 greaterTail 都指向 哨兵位 的节点（不为 NULL）；

动图一👇

动图二👇

动图三👇

把 链表 1 和 链表 2 链接起来

注意：

题目是没有说链表是带 哨兵位 的，所以我们需要先让 lessHead 和 greaterHead 指向 哨兵位 的 下一个节点。

然后再用 链表 1 的 lessTail 去链接 链表 2 的 greaterHead。

3. 代码实现

接口代码

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lessHead, *lessTail, *greaterHead, *greaterTail;
        lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        
        lessTail->next = greaterTail->next = NULL;
        
        struct ListNode* cur = pHead;
        
        while (cur) {
            if (cur->val < x) {
                lessTail->next = cur;
                lessTail = lessTail->next;
            }
            else {
                greaterTail->next = cur;
                greaterTail = greaterTail->next;
            }
            cur = cur->next;
        }
        
        lessTail->next = greaterHead->next;
        greaterTail->next = NULL;
        
        struct ListNode* list = lessHead->next;
        free(lessHead);
        free(greaterHead);
        
        return list;
    }
};