✨hello，进来的小伙伴们，你们好耶！✨
🍖🍖系列专栏：【牛客刷题】
🍈🍈作者简介：一名双非本科大三在读的Java编程小白，启夜星辰，你我同行！
问题描述
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
解题思路：
1、我们可以定义四个节点，bs be 用于存储表示小于x的所有节点,as,ae表示用来存储大于等于x的节点，bs，as永远指向两段链表的头，be,ae指向两段链表的尾巴，这样就省去了每次需要找尾巴的麻烦，然后遍历链表把这些节点都存起来，最后通过be.next = as;将两段链表链接起来。
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode head, int x) {
//根据x，将链表中的数据划分成两部分
//小于x的部分
ListNode bs = null;
ListNode be = null;
//大于x的部分
ListNode as = null;
ListNode ae = null;
while (head != null) {
//判断当前head的val是哪一部分
if (head.val < x) {
//判断是否是第一次插入
if (bs == null) {
bs = head;
be = head;
} else {
be.next = head;
be = be.next;
}
head = head.next;
} else {
if (as == null) {
as = head;
ae = head;
} else {
ae.next = head;
ae = ae.next;
}
head = head.next;
}
}
//链表数据全部大于x
if (bs == null) {
return as;
}
if (as != null) {
ae.next = null;
}
be.next = as;
return bs;
}
}
