给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

    示例 1：
    image.png

    输入：head = [4,2,1,3]
    输出：[1,2,3,4]
    示例 2：

    输入：head = [-1,5,3,4,0]
    输出：[-1,0,3,4,5]
    示例 3：

    输入：head = []
    输出：[]

    提示：

    链表中节点的数目在范围 [0, 5 * 104] 内
    -105 <= Node.val <= 105

    进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode() {}
    7.  *     ListNode(int val) { this.val = val; }
    8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    9.  * }
    10.  */
    11. class Solution {
    12.     /**
    13.     归并排序
    14.      */
    15.     public ListNode sortList(ListNode head) {
    16.         if (head == null || head.next == null) return head;
    17.         ListNode fast = head.next, slow = head;
    18.         while (fast != null && fast.next != null) {
    19.             fast = fast.next.next;
    20.             slow = slow.next;
    21.         }
    22.         //分割
    23.         ListNode next = slow.next;
    24.         slow.next = null;
    25.         ListNode left = sortList(head);
    26.         ListNode right = sortList(next);
    27.         //合并
    28.         ListNode h = new ListNode(0);
    29.         ListNode res = h;
    30.         while (left != null && right != null) {
    31.             if (left.val <= right.val) {
    32.                 h.next = left;
    33.                 left = left.next;
    34.             } else {
    35.                 h.next = right;
    36.                 right = right.next;
    37.             }
    38.             h = h.next;
    39.         }
    40.         h.next = left == null ? right : left;
    41.         return res.next;
    42.     }
    43. }