面试金典题2.4
给你一个链表的头节点 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] 提示：
- 链表中节点的数目在范围
[0, 200]内 -100 <= Node.val <= 100-200 <= x <= 200
其实这道题我一开始还没理解到意思，我以为是要将整个链表的数字进行排序，后面发现其实没那么麻烦，它只需要跟给定的目标值进行比较就好了，比如给定目标值是5，那么只需要一个一个去跟5比较，比5小的放前面，比5大或相等的放后面。说到这里，其实这道题的思路已经出来了，就是去遍历整个链表，然后跟目标值进行比较，比目标值小的放在一个链表里面，比它大的放在另一个链表里面，然后把两个链表连接起来就是最后的结果。
leetcode代码如下
/**
* 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) {
ListNode* s=new ListNode(0);
ListNode* l=new ListNode(0);
ListNode* sh=s;
ListNode* lh=l;
while(head!=nullptr){
if(head->val<x){
s->next=head;
s=s->next;
}else{
l->next=head;
l=l->next;
}
head=head->next;
}
l->next=nullptr;
s->next=lh->next;
return sh->next;
}
};