排序链表（归并排序）

本题要求在 O(n log n) 时间复杂度和常数级空间复杂度下。排序算法中，只有快排、堆和归并排序时间复杂度可以满足要求，但是快排时间复杂度不稳定而且空间复杂度不是常数，堆不适合链表，所以要想到归并排序

 public ListNode sortList(ListNode head) {
    
        return mergeSort(head,null);
    }
    //递归分开阶段
    public ListNode mergeSort(ListNode head,ListNode tail){
    
        if(head == null) return head;
     当只剩下两个结点时，直接断开，否则会一直递归死循环
        if(head.next == tail){
    
            head.next = null;
            return head;
        }
     快慢指针，当快指针走到尾结点，慢指针会走到中间结点。
        ListNode fast = head;
        ListNode slow = head;
        while(fast != tail){
    
            slow = slow.next;
            fast = fast.next;
            if(fast != tail) fast = fast.next; 
        }
      记录中间结点，然后递归
        ListNode mid = slow;
      递归头结点到中间结点
        ListNode sort1 = mergeSort(head,mid);
      递归中间结点到尾结点
      注意此处不能像归并排序一样从中间的下一个开始
        ListNode sort2 = mergeSort(mid,tail);
      合并节阶段
        ListNode res = merge(sort1,sort2);
        return res;
    }
    //合并阶段
    public ListNode merge(ListNode headA,ListNode headB){
    
     建立一个链表头结点
        ListNode dummy = new ListNode();
     临时节点，记录链表的末尾位置
        ListNode temp = dummy;
      
        ListNode tempA = headA;
        ListNode tempB = headB;
     
        while(tempA != null && tempB != null){
    
        把节点值较小的放到前面
            if(tempA.val < tempB.val){
    
                temp.next = tempA;
                tempA = tempA.next;
            }else{
    
                temp.next = tempB;
                tempB = tempB.next;
            }
         链表指针后移
            temp = temp.next;
        }
        当A不为空，说明B已经走完，直接把A剩下的部分加入链表末尾
        if(tempA != null) temp.next = tempA;
        当B不为空时同理
        if(tempB != null) temp.next = tempB;
        返回新建的链表
        return dummy.next;

    }

空间复杂度 log n