【Leetcode】148. Sort List

Question：

Sort a linked list in O(n log n) time using constant space complexity.

Tips：给一个单链表按照val进行排序。

思路：题目要求时间复杂度为nlog（n） 这是归并排序的时间复杂度，即采用分治的方法进行排序。（归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。）

①将链表分为两部分。如果是数组可以直接定位，但是对于链表需要，通过指针才能找到链表中间位置。两个速度不同的指针，可以找到链表的中间位置。

slow=slow.next;
fast=fast.next.next;

②分别将前后两部分排序，这是需采用递归来完成。

③将左右两部分合并。

代码：

 public ListNode sortList(ListNode head) {
         if(head==null ||head.next==null)
             return head;
         ListNode pre=null;
         ListNode slow=head;
         ListNode fast=head;
         //slow将为右半部分的头结点
         while(fast!=null && fast.next!=null){
             pre=slow;
             slow=slow.next;
             fast=fast.next.next;
         }
         pre.next=null;
         //递归的排序左右两部分
         ListNode l1=sortList(head);
         ListNode l2=sortList(slow);
         ListNode list=merge(l1,l2);
        return list;
            
        }
//合并两个链表
    private ListNode merge(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode l=new ListNode(-1);
        ListNode node=l;
        while(l1!=null && l2!=null){
            if(l1.val>=l2.val){
                l.next=l2;
                l2=l2.next;
            }else{
                l.next=l1;
                l1=l1.next;
            }
            l=l.next;
        }
        //l1 l2中有不为空的直接接在后面
        if(l1!=null){
            l.next=l1;
        }
        if(l2!=null){
            l.next=l2;
        }
        return node.next;
    }