单链表的排序

例子:

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

解析：与排序数组类似，用归并排序达到时间复杂度O(nlogn)

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;//递归出口
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;//中点
        }
        ListNode temp = slow.next;//切为两半
        slow.next = null;//切为两半，变成两个链表
        ListNode left =  sortList(head);//结果123
        ListNode right = sortList(temp);//结果45
        ListNode pre = new ListNode(0);
        ListNode h =pre;//pre的位置
        while(left != null && right != null){//merge操作
            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 ? left : right);
        return pre.next;
    }
}