Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

/**
 * 86. Partition List
 * https://leetcode.com/problems/partition-list/
 * https://real-neo.me/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;
    }
}