QUESTION:

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

示例 1:

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

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

EXPLANATION:

当看到复杂度为O（nlogn)的时候，排序算法中也只有快排，堆排和归并排序。那么可以选择采用归并排序的方式来进行，归并排序方式的算法思想我就不在这里一一描述了可以查看这个链接，比较详细。
思路逻辑：
1.采用归并排序的思想，首先找到链表的中点，采用快慢指针的方式
2.将分开的两段分别进行排序，重复1的方式
3.最后将只有一个节点，那么这个节点必然是有序的，然后将这个节点和相邻节点进行排序
4.重复合并操作直到完成整个链表的排序

SOLUTION:

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null) return null;
        return sortListHelper(head);
    }
    public ListNode sortListHelper(ListNode head){
        if(head.next==null) return head;

        ListNode f=head,s=head,sign = head;
        while (f!=null && f.next!=null){
            sign = s ;
            s = s.next;
            f = f.next.next;
        }
        sign.next = null;
        ListNode left = sortListHelper(head);
        ListNode right = sortListHelper(s);
        return sortListMerge(left,right);
    }

    public ListNode sortListMerge(ListNode left,ListNode right){
        ListNode head = new ListNode(0);
        ListNode tmp = head;
        while (left!=null && right!=null){
            if(left.val<right.val){
                tmp.next = left;
                tmp = tmp.next;
                left = left.next;
            }else{
                tmp.next = right;
                tmp = tmp.next;
                right = right.next;
            }
        }
        if(right!=null) tmp.next = right;
        if(left!=null) tmp.next = left;
        return head.next;
    }
}