1、描述

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你不需要保留每个分区中各节点的初始相对位置。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、关键字

分割链表，给定一个值，

3、思路

就是快排的第一步，快排1.0版本，大于等于的放到一起，
快排2.0：荷兰国旗，小等大，分3部分，
快排3.0：搞一个随机数种子来做哨兵。

4、notes

这个题很常规，
就是搞一个哑节点做前导，搞两个链表：，一个小，一个大，然后重新构造新节点，搞成指向，最后链接起来就行了。

5、复杂度

时间：O（N）遍历整个原来的链表
空间：O（N)就是得重新构造n个节点

6、code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        auto h1 = new ListNode(-1);
        auto hh1 = h1;
        auto h2 = new ListNode(-1);
        auto hh2 = h2;

        while(head){
            auto tem = new  ListNode(head->val);
            if(tem->val < x){
                h1->next = tem;
                h1 = h1->next;
            }
            else{
                h2->next = tem;
                h2 = h2->next;
            }
            head = head->next;
        }
        h1->next = hh2->next;
        return hh1->next;
    }
};