左程云算法与数据结构课 https://www.bilibili.com/video/BV13g41157hK?p=2&spm_id_from=pageDriver

题目

给定一个单链表的头节点 head，节点的值类型是整型，再给定一个整数 piovt 。实现一个调整链表的函数，将链表调整为左部分都是值小于 pivot 的节点，中间部分都是值等于 pivot 的节点，右半部分都是值大于 pivot 的节点。要求三个部分内部维持稳定性，时间复杂度为 O(N)，空间复杂度为 O(1)。

题解

设 6 个指针，lH、lT、eH、eT、gH、gT 分别表示小于 pivot 部分的头指针和尾指针、等于 pivot 部分的头指针和尾指针、大于 pivot 部分的头指针和尾指针。扫描链表，根据值与 pivot 的比较结果放到三个部分之一，最后把三个部分连接起来即可。

public class ListPartition {
    public static Node listPartition(Node head, int pivot) {
        Node lH = null; //less head
        Node lT = null; //less tail
        Node eH = null; //equal head
        Node eT = null; //equal tail
        Node gH = null; //greater head
        Node gT = null; //greater tail
        Node next = null;
        //根据节点值分发到三个部分之一
        while (head != null) {
            next = head.next; //保存下一个节点
            head.next = null;
            if (head.value < pivot) {
                if (lH == null) {
                    lH = head;
                    lT = head;
                } else {
                    lT.next = head;
                    lT = head;
                }
            } else if (head.value == pivot) {
                if (eH == null) {
                    eH = head;
                    eT = head;
                } else {
                    eT.next = head;
                    eT = head;
                }
            } else {
                if (gH == null) {
                    gH = head;
                    gT = head;
                } else {
                    gT.next =head;
                    gT = head;
                }
            }
            head = next;
        }
        //小于部分和等于部分合并
        if (lT != null) {
            lT.next = eH;
            eT = eT == null ? lT : eT;
        }
        //合并大于部分
        if (eT != null) {
            eT.next = gH;
        }
        return lH != null ? lH : (eH != null ? eH : gH);
    }
}