共计 3384 个字符，预计需要花费 9 分钟才能阅读完成。
咋一看，仿佛和快排的 partition 过程，也就是荷兰国旗问题很类似，只是此处换成了单链表构造，实际上也的确能够采纳荷兰国旗问题来求解，只是此时的额定空间复杂度为 O(N)。
1、采纳荷兰国旗问题求解：
（1）将链表放到数组中
（2）应用荷兰国旗办法将数组分为小于区、等于区、大于区
（3）将数组从新连成链表，返回头节点
/**
* @author Java 和算法学习：周一
*/
public static Node comparator(Node head, int pivot) {if (head == null) {return null;}
// 获取链表节点数
Node current = head;
int i = 0;
while (current != null) {
i++;
current = current.next;
}
// 将链表放到数组中
Node[] arr = new Node[i];
current = head;
for (i = 0; i < arr.length; i++) {arr[i] = current;
current = current.next;
}
// 将数组分为小于区、等于区、大于区（外围就是荷兰国旗问题）partition(arr, pivot);
// 将数组连成链表
for (i = 1; i < arr.length; i++) {arr[i - 1].next = arr[i];
}
arr[i - 1].next = null;
// 返回头节点
return arr[0];
}
private static void partition(Node[] arr, int pivot) {
int small = -1;
int big = arr.length;
int index = 0;
while (index < big) {if (arr[index].value < pivot) {swap(arr, ++small, index++);
} else if (arr[index].value == pivot) {index++;} else {swap(arr, --big, index);
}
}
}
2、额定空间复杂度为 O(1) 的解法：
（1）应用 6 个变量，顺次示意小于区头节点、尾结点，等于区头节点、尾结点，大于区头节点、尾结点
（2）遍历链表，把节点放到各个局部、同时调整尾结点
（3）将小于区 等于区 大于区 三块头尾连接起来
/**
* @author Java 和算法学习：周一
*/
public static Node smallerEqualBigger(Node head, int pivot) {
// 小于区头节点
Node sH = null;
// 小于区尾节点
Node sT = null;
// 等于区头节点
Node eH = null;
// 等于区尾节点
Node eT = null;
// 大于区头节点
Node bH = null;
// 大于区尾节点
Node bT = null;
// 标记以后遍历的 next 节点
Node next = null;
// 将链表分成 小于区 等于区 大于区 三块
while (head != null) {
// 记录 next 节点
next = head.next;
// 以后节点 next 节点置空
head.next = null;
if (head.value < pivot) {
// 小于区
if (sH == null) {
// 如果是小于区的第一个节点，则小于区的头尾节点都指向以后节点
sH = head;
sT = head;
} else {
// 如果不是小于区的第一个节点，则小于区的尾结点指向以后节点，调整尾结点
// 即在以后区内将各节点再次连接起来
sT.next = head;
sT = head;
}
} else if (head.value == pivot) {
// 等于区
if (eH == null) {
// 如果是等于区的第一个节点，则等于区的头尾节点都指向以后节点
eH = head;
eT = head;
} else {
// 如果不是等于区的第一个节点，则等于区的尾结点指向以后节点，调整尾结点
eT.next = head;
eT = head;
}
} else {
// 大于区
if (bH == null) {
// 如果是大于区的第一个节点，则大于区的头尾节点都指向以后节点
bH = head;
bT = head;
} else {
// 如果不是大于区的第一个节点，则大于区的尾结点指向以后节点，调整尾结点
bT.next = head;
bT = head;
}
}
// 以后节点挪动到 next 节点
head = next;
}
// 将小于区 等于区 大于区 三块头尾连接起来
// 小于区存在
if (sT != null) {
// 则小于区尾节点连贯等于区头节点
sT.next = eH;
// 如果此时等于区尾结点为空（即整个等于区为空），那么等于区的尾结点则为小于区尾结点
// 如果此时等于区尾结点不为空，那么等于区的尾结点就是之前的尾结点
eT = eT == null ? sT : eT;
}
// 有等于区，eT 就是等于区的尾结点
// 无等于区，有小于区，eT 就是小于区的尾结点
// 无等于区，无小于区，eT 就是空
if (eT != null) {
// 则等于区的尾结点连贯大于区头节点
eT.next = bH;
}
// 最初返回以后的头节点
// 有小于区，返回小于区头节点
// 无小于区，有等于区，返回等于区头节点
// 无小于区，无等于区，有大于区，返回大于区头节点
return sH != null ? sH : (eH != null ? eH : bH);
}
本文所有代码：https://github.com/monday-pro/algorithm-study/tree/master/src/basic/node
正文完