题目
给你一个链表的头节点 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]
解题
方法一：创建新的链表
创建两个链表，其中一个值小于x，另外一个大于x
最后再将两者进行合并。
class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode* dummy1=new ListNode(0); ListNode* p1=dummy1; ListNode* dummy2=new ListNode(0); ListNode* p2=dummy2; ListNode* cur=head; while(cur){ if(cur->val<x){ p1->next=cur; p1=p1->next; } else{ p2->next=cur; p2=p2->next; } cur=cur->next; } p2->next = nullptr;//必须要加，因为p2接的是cur，而cur可能不只就一个节点 p1->next=dummy2->next; return dummy1->next; } };
方法二：双指针(原地修改)
慢指针：修改值，变成小于x的
块指针：遇到小于x的，就和慢指针交换
交换节点，无须节点进行交换，只需要值进行交换就行了
class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode* slow=head; ListNode* fast=head; while(fast){ if(fast->val<x){ swap(slow->val,fast->val); slow=slow->next; } fast=fast->next; } return head; } };
