排序链表，要求时间复杂度 O(nlogn)，空间复杂度为常数。

例一：
输入： 4->2->1->3
输出： 1->2->3->4

例二：
输入： -1->5->3->4->0
输出： -1->0->3->4->5

/*
 * 148. Sort List
 * https://leetcode.com/problems/sort-list/
 * https://www.whosneo.com/148-sort-list/
 */

public class SortList {
    public static void main(String[] args) {
        ListNode head = new ListNode(5);
        ListNode node = head;
        node.next = new ListNode(3);
        node = node.next;
        node.next = new ListNode(8);
        node = node.next;
        node.next = new ListNode(4);
        node = node.next;
        node.next = new ListNode(7);
        node = node.next;
        node.next = new ListNode(2);
        node = node.next;
        node.next = new ListNode(9);
        node = node.next;
        node.next = new ListNode(0);
        node = node.next;
        node.next = new ListNode(6);
        node = node.next;
        node.next = new ListNode(1);

        SortList solution = new SortList();
        node = solution.sortList(head);
        solution.print(node);
    }

    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 sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode slow = head, fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;
        slow.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        ListNode prev = new ListNode(0);
        ListNode node = prev;

        while (left != null && right != null) {
            if (left.val < right.val) {
                node.next = left;
                left = left.next;
            } else {
                node.next = right;
                right = right.next;
            }

            node = node.next;
        }

        node.next = left != null ? left : right;

        return prev.next;
    }
}