咋一看，仿佛和快排的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