将单向链表按某值划分成左边小、中间相等、右边大的形式

• 把链表放入数组里，在数组上做 partition（笔试用）
• 分成小、中、大三部分，再把各个部分之间串起来（面试用）

package size;

public class SmallerEqualBigger {
    /**
     * 将单向链表按某值划分成左边小、中间相等、右边大的形式
     * <p>链表直接实现：分成小、中、大三部分，再把各个部分之间串起来</p>
     *
     * @param root  head
     * @param pivot 比较值
     *
     * @return 划分后的链表
     */
    public static Node listPartition(Node root, int pivot) {
        // head -> 小于/等于/大于
        Node sH = null, eH = null, mH = null;
        // tail -> 小于/等于/大于
        Node sT = null, eT = null, mT = null;
        // 下一个指针
        Node next;
        while (root != null) {
            next = root.next;
            root.next = null;
            if (root.value < pivot) {
                if (sH == null) {
                    sH = root;
                } else {
                    sT.next = root;
                }
                sT = root;
            } else if (root.value > pivot) {
                if (mH == null) {
                    mH = root;
                } else {
                    mT.next = root;
                }
                mT = root;
            } else {
                if (eH == null) {
                    eH = root;
                } else {
                    eT.next = root;
                }
                eT = root;
            }
            root = next;
        }
        // 将三个链表链接起来
        if (sT != null) {
            sT.next = eH;
            eT = eT == null ? sT : eT;
        }
        if (eT != null) {
            eT.next = mH;
        }
        return sH != null ? sH : (eH != null ? eH : mT);
    }

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }
}