148. 排序链表

思路：

归并排序

• 递归的终止条件是链表的节点个数小于或等于 1，即当链表为空或者链表只包含 11个节点时，不需要对链表进行拆分和排序。
• 找到链表重点，对链表进行拆分，分别排序，返回两个链表的首结点，对于链表中点的找法可以采用快慢指针，快指针一次走两步，满指针一次走一步，快指针走到最后一个节点的额时候慢指针所在位置为中点
• 最后合并连个有序链表

代码：

class Solution {
        public ListNode sortList(ListNode head) {
            return sortList(head, null);
        }

        //对收尾为head和tail的链表进行排序
        public ListNode sortList(ListNode head, ListNode tail) {
            if (head == null) {
                return null;
            }

            //区间范围，前闭后开 [mid, tail)，tail不包含在内。
            //如果只有一个结点了就不需要再拆了
            if (head.next == tail) {
                head.next=null;
                return head;
            }

            //找到中间结点
            //快指针一次走两步，慢指针一次走一步，快指针到链表末尾时候
            //慢指针指向链表中间位置
            ListNode quick=head,slow=head;
            while (quick!=tail){
                quick=quick.next;
                slow=slow.next;
                //防null,直到quick走到最后一个结点
                if (quick!=tail){
                    quick=quick.next;
                }
            }
            //区间范围，前闭后开 [mid, tail)，tail不包含在内。
            ListNode listNode1 = sortList(head, slow);
            ListNode listNode2 = sortList(slow, tail);
            //合并两个有序链表,返回合并链表头结点
            ListNode res=merge(listNode1,listNode2);
            return res;
        }


        //合并两个有序链表,返回合并链表头结点
        private ListNode merge(ListNode listNode1, ListNode listNode2) {
            ListNode pre=new ListNode(0);
            ListNode curr=pre,temp1=listNode1,temp2=listNode2;
            while (temp1!=null&&temp2!=null){
                if (temp1.val<temp2.val){
                    curr.next=temp1;
                    temp1=temp1.next;
                }else {
                    curr.next=temp2;
                    temp2=temp2.next;
                }
                curr=curr.next;
            }

            if (temp1==null){
                curr.next=temp2;
            }
            if (temp2==null){
                curr.next=temp1;
            }
            return pre.next;
        }
    }