在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }

    private ListNode mergeSort(ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }

        // 找链表的中点
        ListNode slow = node;
        ListNode fast = node.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 此时slow为中点

        // 对右边进行归并排序
        ListNode right = mergeSort(slow.next);

        // 断开节点
        slow.next = null;

        // 对左边进行归并排序
        ListNode left = mergeSort(node);

        return mergeList(left, right);
    }

    // 合并两个有序的列表
    private ListNode mergeList(ListNode left, ListNode right) {
        ListNode newNode = new ListNode(-1);
        ListNode temp = newNode;
        while (left != null && right != null) {
            if (left.val < right.val) {
                temp.next = left;
                left = left.next;
            } else {
                temp.next = right;
                right = right.next;
            }
            temp = temp.next;
        }

        temp.next = left == null ? right : left;
        return newNode.next;
    }
}