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

第一种方法：准备三个队列，遍历链表时候，将小于的放入小于队列中，等于的放入等于队列中，大于的放入大于队列中，然后从队列中取出来重新连接

第二种方法：遍历链表，组成三个链表，重新连接  （只用到了有限的几个变量，额外空间复杂度是O（1））

/**
 *  1.将链表分为三部分：  small，equal，big
 *                 small：1->2->null
 *                 equal：5->5->null
 *                 big：9->8->null
 *  2.将small、equal、big三个链表重新串起来
 *  3.整个过程需要特别注意对null节点的判断和处理
 *
 */

public class SmallEqualBig {

    public static void main(String[] args) {

        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(9);
        head.next.next.next = new Node(5);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(8);
        display(head);
        //将链表打断后重新连接
        Node newHead = partition(head,5);
        display(newHead);
        
    }

   public static  void display(Node first) {
        StringBuilder sb = new StringBuilder();
        while (first != null) {
            sb.append(first.val + " -> ");
            first = first.next;
        }
        String res = sb.substring(0, sb.lastIndexOf(" -> "));
        System.out.println(res);
    }
    
    public static Node partition(Node head, int pivot) {

        // 将链表分为small、equal、big
        Node sH = null;
        Node sT = null;
        Node eH = null;
        Node eT = null;
        Node bH = null;
        Node bT = null;
        Node next = null;// 保存下一个节点

        // 将所有的节点依次保存在三个链表中
        while (head != null) {
            //保存下一个节点
            next = head.next;
            //将head节点指向null
            head.next = null;
            if (head.val < pivot) {
                if (sH == null) {
                    sH = head;
                    sT = head;
                } else {
                    sT.next = head;
                    sT = head;
                }
            } else if (head.val == 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;
                }
            }
            head = next;
        }

        // 小的和相等的重新连接
        if (sT != null) {
            sT.next = eH;
            //假如中间部分为空
            eT = eT == null ? sT : eT;
        }
        // 所有的重新连接
        if (eT != null) {
            eT.next = bH;
        }
        // 判断头节点是否为空，三个子链表，哪个部分不为null,就返回哪个
        return sH != null ? sH : eH != null ? eH : bH;
    }

    public static class Node {
        int val;
        Node next;

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

}