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

示例 1：

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

解题思路

归并排序

1. 递归终止条件：如果链表为空或只有一个节点，无需排序
2. 用快慢指针找到中点，并切断链表，left 和 right 分别表示左右两边的头
3. 递归排序左右两部分
4. 合并两个有序链表（参考 leetcode 21 合并两个有序链表 ）

Java 实现

public ListNode sortList(ListNode head) {
    // 1. 递归终止条件：如果链表为空或只有一个节点，无需排序
    if (head == null || head.next == null){
        return head;
    }
    // 2. 找到中点并切断链表
    ListNode mid = getMid(head);
    ListNode left = head;
    ListNode right = mid.next;
    mid.next = null; // 切断链表

    // 3. 递归排序左右两部分
    left = sortList(left);
    right = sortList(right);

    // 4. 合并两个有序链表
    return merge(left, right);
}

/**
 * 快慢指针找链表的中点
 */
private ListNode getMid(ListNode head){
    ListNode fast = head;
    ListNode slow = head;
    // 快慢指针找中点一定要确保 fast.next.next 有效 。slow是前一半的最后一个节点。
    while(fast.next != null && fast.next.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

/**
 * 归并（合并两个有序链表）
 */
private ListNode merge(ListNode l1, ListNode l2){
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (l1 != null && l2 != null){
        if (l1.val > l2.val){
            curr.next = l2;
            l2 = l2.next;
        } else {
            curr.next = l1;
            l1 = l1.next;
        }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}