题解 | #单链表的排序#TOP12

思路:
1.题目是O(Nlog(n))时间负责度，当然我们第一眼可能想到，直接用辅助数组排序，然后将辅助数组辅助到链表上，可以做到数组时间O(Nlog(n)),但是数组空间O(N)，题目没说，也是可以的
2.用归并排序，自顶向下，时间复杂度O(Nlog(N))，无空间消耗，拆分后就是合并两个有序的链表而已。

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        if(head == null || head.next == null){
            return head;
        }
//         List<Integer> temp = new ArrayList<>();
        
//        ListNode currentNode = head;
//         while(currentNode != null){
//             temp.add(currentNode.val);
//             currentNode = currentNode.next;
//         }
//         int[] data = new int[temp.size()];
//         for(int i = 0;i<temp.size();i++){
//             data[i] = temp.get(i);
//         }
        
//         Arrays.sort(data);
        
//         ListNode newHead = new ListNode(-1);
//         ListNode tempNode = newHead;
//         for(int i : data){
//             ListNode  cur = new ListNode(i);
//             tempNode.next = cur;
//             tempNode = cur;
//         }
        //题目是时间负责度O(NlogN)
        //使用归并排序，自顶向下
        ListNode fast = head.next, slow  = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //[head , slow], [temp, end];
        ListNode temp = slow.next;
        slow.next = null;
        ListNode left = sortInList(head);
        ListNode right = sortInList(temp);
        ListNode newHead = new ListNode(-1);
        ListNode currentNode = newHead;
        while(left != null && right != null){
            if(left.val < right.val){
                currentNode.next = left;
                left = left.next;
            }else{
                currentNode.next=  right;
                right = right.next;
                
            }
            currentNode = currentNode.next;
        }
        currentNode.next = left != null ? left :right;
        return newHead.next;
    }
}