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

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

思路：

使用两个链表分别保存小于和大于等于的部分即可。

详见：
链接：https://leetcode.cn/problems/partition-list/solutions/2362068/86-fen-ge-lian-biao-shuang-zhi-zhen-qing-hha7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

//使用两个链表

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode * lower = new ListNode(0,nullptr);
        ListNode * higher = new ListNode(0,nullptr);
        ListNode * tmp_l = lower;
        ListNode * tmp_h = higher;

        ListNode * tmp = head;
        ListNode * cur = head;

        while(tmp!=nullptr){
            if(tmp->val < x){
                tmp_l->next = tmp;
                tmp_l = tmp_l->next;
            }
            else{
                tmp_h->next = tmp;
                tmp_h=tmp_h->next;
            }
            cur = tmp->next;
            tmp->next = nullptr;
            tmp = cur;
        }

        tmp_l->next = higher->next;
        return lower->next;
    }
};