题目链接：leetcode86
题目大意
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 相对位置不变相当于稳定地区分，比如两个相等的数原本的位置划分后不能更改这个相对位置，不同的数更是如此。
解题思路
双指针
可以维护两个链表，最后把头尾连起来即可，链表hl表示小于x的数字链表，hr表示大于或者等于x的数字链表。由于题意并不是只是单纯的把数字划分开，还要保证相对位置不变，所以在维护的同时不能使用头插法，否则最后还要多一个逆置的复杂度，注意后面的链表可能结尾并不是NULL，要特判一下，避免内存错误等问题。
代码实现
class Solution {
public:
ListNode
* partition(ListNode
* head
, int x
) {
if (head
== NULL || head
->next
== NULL) return head
;
ListNode
*l
= NULL, *r
= NULL, *hl
= NULL, *hr
= NULL;
while (head
) {
if (head
->val
< x
) {
if (l
) l
->next
= head
;
l
= head
;
if (!hl
) hl
= l
;
} else {
if (r
) r
->next
= head
;
r
= head
;
if (!hr
) hr
= r
;
}
head
= head
->next
;
}
if (hr
) {
r
->next
= NULL;
}
if (hl
) {
l
->next
= hr
;
return hl
;
}
return hr
;
}
};
