给你一个链表的头节点 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;}
};