【来不及刷题之】37、排序链表（链表归并排序）

• 使用直接插入排序时间复杂度太多无法通过，使用归并排序，主要有三个步骤：
  • 1. 寻找链表的中间结点，断开成两个等长的链表
  • 1. 对这两个链表分别排序 （递归）
  • 1. 合并两个排序链表
• 思路比较简单，但是这里寻找中间结点的时候有一个很大坑
• 寻找链表的中间节点不能直接照搬 876题，因为那个题目中，如果节点个数为偶数，返回值指向的是右侧链表的第一个节点
• 然而，为了断开成两个等长的链表，这个题目中，mid应该指向左侧链表的最后一个节点才对。因此初始化需要做出调整：quick=head.next; 而不是quick=head;

 public ListNode sortList(ListNode head) {
        if(head==null || head.next==null)
            return head;
        ListNode mid=findMid(head); // 找到链表的中点，偶数个结点时，mid指向左侧链表的最后一个
        ListNode left=head;
        ListNode right=mid.next;
        mid.next=null; // 断开成左右两个链表
        ListNode l1 = sortList(left); // 排序左侧链表
        ListNode l2 = sortList(right);// 排序右侧链表
        return mergeTwoList(l1,l2); // 合并两个有序链表

    }

     public ListNode findMid(ListNode head){
        ListNode slow=head,quick=head.next;// 为了保证偶数时指向的是左侧链表的最后一个，必须为quick=head.next
        while (quick!=null && quick.next!=null){
            slow=slow.next;
            quick=quick.next.next;
        }
        return slow;
    }

     public ListNode mergeTwoList(ListNode head1, ListNode head2){
        ListNode dummy=new ListNode();
        ListNode p=head1,q=head2,k=dummy;
        while (p!=null && q!=null){
            if(p.val<q.val){
                k.next=p;
                p=p.next;
            }else{
                k.next=q;
                q=q.next;
            } // 注意，这里没有必要让pq结点指向空，因为原本两个链表的尾结点自己会指向空
            k=k.next;
        }
        //pq结点不可能同时为空
        k.next=q==null?p:q;
        return dummy.next;
    }