# 86.分割链表

1.这道题要求我们划分链表，把所有小于给定值的节点都移到前面，大于该值的节点顺序不变，相当于一个局部排序的问题。那么可以想到的一种解法是首先找到第一个大于或等于给定值的节点，用题目中给的例子来说就是先找到4，然后再找小于3的值，每找到一个就将其取出置于4之前即可。

``````    ListNode* partition(ListNode* head, int x) {
ListNode* dummy = new ListNode(-1);
ListNode* newDummy = new ListNode(-1);
ListNode* cur = dummy, *p = newDummy;
while (cur->next)
{
if (cur->next->val < x)
{
p->next = cur->next;
p = p->next;
cur->next = cur->next->next;
p->next = NULL;
}
else
{
cur = cur->next;
}
}
p->next = dummy->next;
return newDummy->next;
}
``````

2、将小于x的数组成一个链表1，大于x的数组成一个链表2，然后将两个链表连接起来。

``````    ListNode* partition2(ListNode* head, int x)
{
ListNode* list1 = new ListNode(0);
ListNode* list2 = new ListNode(0);
ListNode* small = list1, *big = list2;
{
{
small = small->next;
}
else
{
big = big->next;
}
}
big->next = NULL;
small->next = list2->next;
return list1->next;
}
``````

``````#include
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* dummy = new ListNode(-1);
ListNode* newDummy = new ListNode(-1);
ListNode* cur = dummy, *p = newDummy;
while (cur->next)
{
if (cur->next->val < x)
{
p->next = cur->next;
p = p->next;
cur->next = cur->next->next;
p->next = NULL;
}
else
{
cur = cur->next;
}
}
p->next = dummy->next;
return newDummy->next;
}

void insertNode(ListNode* p, int i)
{
ListNode* node = new ListNode(1);
node->val = i;
node->next = p->next;
p->next = node;
}

{
ListNode* list1 = new ListNode(0);
ListNode* list2 = new ListNode(0);
ListNode* small = list1, *big = list2;
{
{
small = small->next;
}
else
{
big = big->next;
}
}
big->next = NULL;
small->next = list2->next;
return list1->next;
}
};

int main(int argc, char* argv[])
{
int a[] = { 1, 4, 3, 2, 5, 2 };
ListNode*test = new ListNode(1);
for (int i : a)
{
Solution().insertNode(test, i);
}
auto res = Solution().partition2(test, 3);
return 0;
}

``````