将一个单向链表按照某个值划分为左边小、中间相等、右边大的形式
问题重述：
给定一个单向链表的头节点，节点的类型是整形，在给定一个整数pivot，实现一个调整链表的函数，将链表划分成左边都是小于pivot的结点，中间都是等于的结点，右边都是大于的结点（调整后的结点顺序不做要求）
进阶：左中右的结点顺序与原链表中的顺序相同，并且时间复杂度达到O（N），空间复杂度达到O（1）
问题分析：
这道题的重点是排序方式，链表的排序不容易，但是数组的排序很简单，我们可以将链表添加到数组中去，然后在数组中进行排序，排完序后再变成链表就可以
对于进阶题，我们不能创建数组来解决，那么我们可以在遍历链表的过程中，将三种类型的结点划分开，然后最后将链表合并起来就是我们要的结果
解法：
普通解法：将所有的值加入到数组中，在数组中进行排序，排完序后再重新连接
进阶解法：将链表划分成三个链表，遍历链表，符合哪一个要求就加入到哪一个链表中去，最后将三个链表连接起来返回就可以
解题：
代码：
普通：
public static Node listPartition1(Node head,int pivot) {
if(head == null) {
return head;
}
Node cur = head;
int i = 0;
while(cur != null) {
i++;
cur = cur.next;
}
Node[] nodeArr = new Node[i];
i = 0;
cur = head;
for(i = 0;i < nodeArr.length;i++) {
nodeArr[i] = cur;
cur = cur.next;
}
arrPartition(nodeArr,pivot);
for(i = 1;i != nodeArr.length;i++) {
nodeArr[i-1].next = nodeArr[i];
}
nodeArr[i-1].next = null;
return nodeArr[0];
}
public static void arrPartition(Node[] nodeArr, int pivot) {
int small = -1;
int big = nodeArr.length;
int index = 0;
while(index != big) {
if(nodeArr[index].value < pivot) {
swap(nodeArr,++small,index++);
}else if(nodeArr[index].value == pivot) {
index++;
}else {
// 这里的index不加1的原因是此时index的值是big所对应的值，需要重新比较
swap(nodeArr,--big,index);
}
}
}
/**
* 交换结点的方法
* @param nodeArr
* @param a
* @param b
*/
public static void swap(Node[] nodeArr,int a,int b) {
Node temp = nodeArr[a];
nodeArr[a] = nodeArr[b];
nodeArr[b] = temp;
}
代码解析：这段代码重点在于排序，除了排序过程，其他过程都一目了然。排序过程使用了一部分的快排思想，对数组中的每一个元素的值和pivot进行比较，如果比该值小，那么就将当前的值和首部指针对应的数组元素进行置换，然后将当前指针前进一格（置换之后直接更新当前指针的原因是，首部指针当前对应的值一定是小于pivot的（small一开始是-1，后面每次更新的值都是小于pivot的值），并且题目不要求顺序），如果当前指针对应的值等于pivot，那么直接更新指针，如果当前指针对应的值大于pivot，将当前指针对应的值和尾部指针对应的元素进行置换，需要注意的是，置换完成之后，当前的index的大小是不确定的，我们需要再次对该值进行比较，所以index不能直接更新。
进阶
public static Node listPartition2(Node head,int pivot) {
if(head == null) {
return head;
}
// 定义三段链表分别为大链表小链表和等于链表
Node smallHead = null;
Node smallTail = null;
Node equalHead = null;
Node equalTail = null;
Node bigHead = null;
Node bigTail = null;
Node next = null;
// 对链表进行遍历
while(head != null) {
// 将head的下一个结点设置为null，方便加入我们的新链表中
next = head.next;
head.next = null;
if(head.value < pivot) {
// 小于则加入小链表中
if(smallHead == null) {
// 小链表为null，则head既为头也为尾
smallHead = head;
smallTail = head;
}else {
// 小链表不为null，则将head添加到尾部（因为题目要求按照原顺序）
smallTail.next = head;
smallTail = head;
}
}else if(head.value == pivot) {
// 等于则加入等于链表中
if(equalHead == null) {
// 等于链表为null，则head既为头也为尾
equalHead = head;
equalTail = head;
}else {
// 等于链表不为null，则将head添加到尾部（因为题目要求按照原顺序）
equalTail.next = head;
equalTail = head;
}
}else {
// 既不小于也不等于，那么就是大于
if(bigHead == null) {
bigHead = head;
bigTail = head;
}else {
bigTail.next = head;
bigTail = head;
}
}
head = next;
}
// 循环完成后，我们将三个链表联结起来就可以
if(smallTail != null) {
smallTail.next = equalHead;
equalTail = (equalTail == null ? smallTail : equalTail);
}
if(equalTail != null) {
equalTail.next = bigHead;
}
return smallHead != null ? smallHead : (equalHead != null ? equalHead : bigHead);
}
代码解析：就是定义三段链表，然后遍历原链表，将链表结点的值和pivot进行比较，按照类别加入不同的链表中，最后将三个链表联结起来，需要注意链表为null的情况
总结：
快速排序的方法：
- 首先确定一个基准数（pivot），这个值可以随机取，也可以取第一个值（我们一般取第一个值，如果基准值不是第一个值，我们可以把那个值和第一个值交换位置）
- 定义两个指针，分别指向所有值的首尾，将第一个元素保存起来，将首部指针置空
- 左右指针交替和基准值进行比较，先用右指针进行比较
如果右边指针大于基准值，右边指针往左移，继续和基准值进行比较
如果小于基准值，将右边指针对应的值移动到左边指针对应的位置，然后左指针右移，开始对左指针的值和基准值进行比较 - 左指针和基准值进行比较
如果左边指针小于基准值，左边指针右移，继续和基准值进行比较
如果大于基准值，就把左边指针对应的值移动到右边指针对应的位置，然后右指针左移，循环3、4的操作 - 最后等到左右指针指向同一位置的时候，将基准值加入到这个位置，此时这些数在基准值左边的元素都小于基准值，大于基准值的元素都大于基准值
- 最后，使用递归的方法对基准值左边元素和基准值右边元素分别进行排序