面试金典题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;
    }
};