给定一个链表和一个值 x，将链表中所有值小于 x 的节点移动到值大于等于 x 的节点之前。

在分隔成的两部分中，你应当保留原有的节点相对顺序。

举例：
输入： head = 1->4->3->2->5->2, x = 3
输出： 1->2->2->4->3->5

/*
 * 86. Partition List
 * https://leetcode.com/problems/partition-list/
 * https://www.whosneo.com/86-partition-list/
 */

class PartitionList {
    public static void main(String[] args) {
        ListNode head = new ListNode(10);
        ListNode node = head;
        for (int i = 9; i > 0; i--) {
            node.next = new ListNode(i);
            node = node.next;
        }

        PartitionList solution = new PartitionList();

        solution.print(head);
        System.out.println("x=3");
        head = solution.partition(head, 3);
        solution.print(head);
        System.out.println("x=7");
        head = solution.partition(head, 7);
        solution.print(head);
    }

    private void print(ListNode node) {
        for (; node != null; node = node.next) {
            System.out.print(node.val);
            System.out.print("->");
        }
        System.out.println("null");
    }

    private ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null)
            return head;
        ListNode node = head;
        ListNode small = null, smallHead = null;
        ListNode big = null, bigHead = null;
        while (node != null) {
            if (node.val < x) { //小链表
                if (small == null) { //第一次找到小的节点
                    small = node;
                    smallHead = node; //记录小链表头部
                } else {
                    small.next = node;
                    small = small.next;
                }
            } else { //大链表
                if (big == null) { //第一次找到大的节点
                    big = node;
                    bigHead = node; //记录大链表头部
                } else {
                    big.next = node;
                    big = big.next;
                }
            }

            node = node.next;
        }

        if (big != null) //若有大链表
            big.next = null; //将大链表最后指向空

        if (small != null) //若有小链表
            small.next = bigHead; //将小链表最后指向大链表
        else //没有小链表
            smallHead = bigHead; //使用大链表替代头部

        return smallHead;
    }
}