148. Sorting linked list

1、 Title Description

 2、 Topic analysis

According to the meaning , Sort the linked list into 【 Ascending 】 Pattern .

The picture above is very clear .

1、 Find the linked list 【 Intermediate nodes 】(LeetCode-876 topic , May refer to ：876. The middle node of a list )

2、 Sort two linked lists 【 Merge two ordered lists 】（LeetCode21 topic , May refer to ：21. Merge two ordered lists ）

3、 Recursion above 1 and 2 Step by step .

Therefore, generally complex topics are several simple topics 【 Sum up and 】.

So the code is as follows ：

class Solution {
public ListNode sortList(ListNode head) {
        // 1、 Recursion end condition 
        if (head == null || head.next == null) {
            return head;
        }

        // 2、 Find the middle node of the linked list and disconnect the linked list  &  Recursive downward exploration 
        // Split the list , Divide and conquer 
        ListNode middle = getMiddle(head);
        // The second half 
        ListNode rightHead = middle.next;
        // The first half is separated in the middle 
        middle.next = null;

        // Split recursively and sequentially 
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);
        
        // 3、 Current layer business operations （ Merge ordered linked list ）
        return mergeListNode(left,right);
    }

    // Get intermediate nodes  LeetCode-876
    private ListNode getMiddle(ListNode head){
          if(head == null || head.next == null)
                  return head;
          ListNode slow = head;
          ListNode fast = head.next;
          while(fast != null && fast.next != null){
              slow = slow.next;
              fast = fast.next.next;
          }
          return slow;
    }

    // Merge and sort two linked lists 【 Ascending 】 LeetCode-21
    private ListNode mergeListNode(ListNode left, ListNode right){
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;

        while(left != null && right != null){
            if(left.val < right.val){
                curr.next =left;
                left = left.next;
            }else{
                curr.next = right;
                right = right.next;
            }
            curr = curr.next;
        }
        curr.next = (left!=null)?left : right;
        return dummy.next;
    }
}

Complexity analysis

Time complexity ：O(nlogn), among n  It's the length of the list .

Spatial complexity ：O(logn), among n  It's the length of the list . The space complexity mainly depends on the stack space of recursive calls