题目入口📌：链表分割
问题描述
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
解题分析
本题比较难理解，我画图来向大家分析。如下图，规定 x = 10，定义一个cur变量且cur 指向链表首部，当cur遍历一次链表，同时把小于10的结点放在 before 链表中，其余的放在 after 链表中。（动图做的有点粗糙，请大家原谅😂）
在图中我们发现，在 before 中，8 比 6 大，但是8 排在 6 的前面是因为在原链表中，8 就排在 6 的前面，这就是题目中不能改变原来的数据顺序的意思。
而图中的 before 和 after 链表都是虚构的，那我们写代码时该如何实现呢？
我们来拿 before 链表 实现来说，我们可以创建两个结点 bs 和 be 来分别表示 before 链表的头和尾，初始化置为空。
创建bs 作用：方便我们找到 before 链表
创建be 作用：方便我们在 before 链表中添加结点
当cur指向结点值小于x，这时如果 bs 和 be 都为空时，那就把cur赋值给bs 和 be。
如果 bs 和 be 都不为空，那么就把cur赋值给 be.next，然后be向后移【be = be.next】
if(bs == null && be == null){//说明before链表中没有元素 bs = cur; be = be; }else{ be.next = cur; be = be.next;//也可以写成be = cur; }
对 after 链表来说，我们也要创建两个结点 as 和 ae，分别指向 after 链表的头和尾。
这一部分具体代码如下
while(cur != null){ if(cur.val < x){ //小于x 则进入 before 链表 if(bs ==null){ bs = cur; be = bs; }else{ be.next = cur; be = be.next; } }else{ //其他情况 则进入 after 链表 if(as ==null){ as = cur; ae = as; }else{ ae.next = cur; ae = cur; } } cur = cur.next; }
最后我要把 before 链表 和 after 链表 合并,同时把ae.next 置为null。
be.next = as; ae.next = null;
到这还没结束，我们还少考虑两种情况
1、after 链表为空
如下图，当 after 链表为空时，我们可以直接返回 bs 。而如果我们让编译器继续执行 ae.next = null 语句那么就会报出空指针异常。
2、before 链表空
如下图，当 before 链表为空时，也不需要执行 be.next = as 语句 ，直接返会 as 即可。
代码实现
public class Partition { public ListNode partition(ListNode pHead, int x) { if(pHead == null) return null; ListNode bs = null; ListNode be = null; ListNode as = null; ListNode ae = null; ListNode cur = pHead; while(cur != null){ if(cur.val < x){ if(bs ==null){ bs = cur; be = bs; }else{ be.next = cur; be = be.next; } }else{ if(as ==null){ as = cur; ae = as; }else{ ae.next = cur; ae = cur; } } cur = cur.next; } if(bs == null){ return as; } if(as == null){ return bs; } be.next = as; ae.next = null; return bs; } }
