排序

桶排序

148. 排序链表 - 力扣（LeetCode）

             sortList(head)
                   │
      ┌────────────┴─────────────┐
      │ 是否只有 0 或 1 个节点？ │
      └───────┬────────┬─────────┘
              │是       │否
              ▼         ▼
       返回 head   找中点 slow
                    pre.next = null
                    │
                    ▼
         ┌───────────────┴───────────────┐
         │                               │
 sortList(leftHalf)              sortList(rightHalf)
         │                               │
    ┌────┴────┐                    ┌────┴────┐
    │ 递归返回 │                    │ 递归返回 │
    │ 有序左链 │                    │ 有序右链 │
    └────┬────┘                    └────┬────┘
         ▼                               ▼
           ┌──────────────┴──────────────┐
           │ merge(有序左链, 有序右链)   │
           └──────────────┬──────────────┘
                          ▼
                     返回合并后的有序链表

                sortList([4,2,1,3])
                 /               \
    sortList([4,2])           sortList([1,3])
       /      \                 /       \
 [4]         [2]            [1]         [3]
  |           |              |           |
 merge([4],[2])= [2,4]   merge([1],[3])= [1,3]
           \                 /
            merge([2,4],[1,3])
                 = [1,2,3,4]

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        //找中点
        ListNode slow = head,fast = head,pre = null;
        while(fast != null && fast.next != null){
            pre = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        pre.next = null;
       ListNode l1 =  sortList(head);
       ListNode l2 =  sortList(slow);
       return merge(l1,l2);

    }
    ListNode merge(ListNode l1,ListNode l2){
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = (l1 == null) ? l2 : l1;
        return dummy.next;
    }
}