排序链表（递归）

题目链接：https://leetcode.cn/problems/sort-list/

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

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

解题思路：
1.找到链表的中点，以中点为分界，将链表拆分成两个子链表。

2.对两个子链表分别排序。

3.将两个排序后的子链表合并，得到完整的排序后的链表。

代码如下：

public class Main {
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;

        //找到链表中点,tmp指向中点的下一个，用于隔断链表
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;

        //递归
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);

        ListNode h = new ListNode(-1);
        ListNode res = h;
        while (left != null && right != null){
            if (left.val <= right.val){
                h.next = left;
                left = left.next;
            }
            else{
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = (left == null?right:left);
        return res.next;
    }
}