Sort linked list (merge sort)

This question requires that O(n log n) Under time complexity and constant space complexity . In the sorting algorithm , Only quick platoon 、 The time complexity of heap and merge sort can meet the requirements , But the time complexity of fast scheduling is unstable and the space complexity is not constant , Heap is not suitable for linked list , So think about merging and sorting

 public ListNode sortList(ListNode head) {
    
        return mergeSort(head,null);
    }
    // Recursively separate stages 
    public ListNode mergeSort(ListNode head,ListNode tail){
    
        if(head == null) return head;
      When there are only two nodes left , Directly disconnect , Otherwise, it will be recursive forever 
        if(head.next == tail){
    
            head.next = null;
            return head;
        }
      Speed pointer , When the fast pointer reaches the tail node , The slow pointer will go to the middle node .
        ListNode fast = head;
        ListNode slow = head;
        while(fast != tail){
    
            slow = slow.next;
            fast = fast.next;
            if(fast != tail) fast = fast.next; 
        }
       Record intermediate nodes , Then a recursive 
        ListNode mid = slow;
       Recursion from head node to intermediate node 
        ListNode sort1 = mergeSort(head,mid);
       Recursion from intermediate node to tail node 
       Note that you cannot start from the next in the middle like merge sorting 
        ListNode sort2 = mergeSort(mid,tail);
       Merge section stage 
        ListNode res = merge(sort1,sort2);
        return res;
    }
    // Consolidation phase 
    public ListNode merge(ListNode headA,ListNode headB){
    
      Create a chain header node 
        ListNode dummy = new ListNode();
      Temporary node , Record the end position of the linked list 
        ListNode temp = dummy;
      
        ListNode tempA = headA;
        ListNode tempB = headB;
     
        while(tempA != null && tempB != null){
    
         Put the smaller node value in front 
            if(tempA.val < tempB.val){
    
                temp.next = tempA;
                tempA = tempA.next;
            }else{
    
                temp.next = tempB;
                tempB = tempB.next;
            }
          Linked list pointer backward 
            temp = temp.next;
        }
         When A Not empty , explain B It's over , Put... Directly A The rest is added to the end of the linked list 
        if(tempA != null) temp.next = tempA;
         When B The same is true when it is not empty 
        if(tempB != null) temp.next = tempB;
         Return to the new linked list 
        return dummy.next;

    }

Spatial complexity log n