原题目（https://leetcode-cn.com/problems/partition-list/）：
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
第一次做这个题没有注意到结果要保持相对位置不变，把它和快排联系到了一起，快排的partition部分也是有一个类似的方法，我就把链表存储到了vector中，用挖坑法完成了题目，能够把两部分分割开来，但是顺序不对：
class Solution { public: ListNode* partition(ListNode* head, int x) { if (head == NULL) { return head; } ListNode* next = head; vector<int> vlist; while(next != NULL) { vlist.emplace_back(next->val); next = next->next; } int left = 0; int right = vlist.size()-1; int dir = 1; //从做往右扫 while(left < right) { if (dir == 1) { if (vlist[left] >= x) { dir = -1; } else { left++; } } else if (dir == -1) { if (vlist[right] < x) { //交换两个值 int tmp = vlist[right]; vlist[right] = vlist[left]; vlist[left] = tmp; dir = 1; } else { right--; } } } next = head; int index = 0; while(next != NULL) { next->val = vlist[index]; index++; next = next->next; } return head; } };
后面看了leetcode官方的解答，看了一眼就看不下去了，在后面又看到另一个简短的c++答案，思想很简单：直接交换就完事了，先判断一下第一个节点是不是大于等于x，后面就是断开链表再连到前面即可，人狠话不多啊，
先介绍下具体的思想：
step 1：如果表头的val比x大，往后找到比x小的节点，把这个节点取出来链接在head前面，再把head指向这个节点；
step 2: 定义两个节点指针，cur和pre，cur始终指向第一个比x大的节点前面的节点，不断移动pre节点寻找val比x小的节点，找到后放在cur后面，将cur跟新为这个新节点
实现的代码如下：
class Solution { public: ListNode* partition(ListNode* head, int x) { if (head == NULL) { return head; } ListNode* pre = head; // 将第一个节点替换为比x小的节点 if (head->val >= x) { while (NULL != pre->next) { if (pre->next->val < x) { ListNode* tmp = pre->next; pre->next = tmp->next; tmp->next = head; head = tmp; break; } else { pre = pre->next; } } } // 找到比x小的节点并将其 pre = head; ListNode* cur = head; while(NULL != pre->next) { if (pre->next->val < x) { if (pre == cur) { cur = cur->next; pre = pre->next; } else { ListNode* tmp = pre->next; pre->next = tmp->next; tmp->next = cur->next; cur->next = tmp; cur = tmp; } } else { pre = pre->next; } } return head; } };
需要注意的是：遍历链表的方式，我第一开始没有领会这种遍历方法的精髓，只是想着模仿题解写了一个答案，后面我想尝试直接使用node!=NULL作为循环条件，发现不可以，为什么呢？
因为我把节点的父节点丢了，没法完成链表截取了，使用node->next!=NULL进行遍历可以一直保留父节点指针
原文：https://www.cnblogs.com/rulin/p/12995721.html