148. 排序链表

1、题目描述

 2、题目分析

根据题意，把链表排序成【升序】模式。

上面这个图很清晰。

1、找到链表的【中间节点】(LeetCode-876题，可参考：876. 链表的中间结点)

2、两个链表进行排序【合并两个有序链表】（LeetCode21题，可参考：21. 合并两个有序链表）

3、递归上面的1和2步骤即可。

所以一般复杂的题目是几道简单题目的【汇总和】。

所以代码如下：

class Solution {
public ListNode sortList(ListNode head) {
        // 1、递归结束条件
        if (head == null || head.next == null) {
            return head;
        }

        // 2、找到链表中间节点并断开链表 & 递归下探
        //拆分链表，分治处理
        ListNode middle = getMiddle(head);
        //后半段
        ListNode rightHead = middle.next;
        //前半段中间分开
        middle.next = null;

        //分别递归依次拆分
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);
        
        // 3、当前层业务操作（合并有序链表）
        return mergeListNode(left,right);
    }

    //获取中间节点 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;
    }

    //两个链表进行合并排序【升序】 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;
    }
}

复杂度分析

时间复杂度：O(nlogn)，其中 n 是链表的长度。

空间复杂度：O(logn)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间