148.排序链表(归并、快排)

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

输入：head = [4,2,1,3] 输出：[1,2,3,4]

1. 归并排序：1.快慢指针找到中点2.递归调用sort()继续分成两半3.分到最底层的时候开始两两合并返回链表。这里要注意的是整个过程是自顶向下再自下向上，这里merge()和sort()函数返回的链表都是有序的；找到中点后要先从中点断链，才继续对前半部分和后半部分递归排序。时间O(nlogn)，因为递归占用了栈空间，因此空间O(longn)。

 public ListNode sortList(ListNode head) {
            if(head==null)
            return head;
            ListNode tail=head;
            while(tail.next!=null) tail=tail.next;
            return sort(head,tail);
    }
    public ListNode sort(ListNode left,ListNode right)
    {
        if(left==right)
        return left;
        ListNode slow=left,fast=left.next;
        while(fast!=null&&fast.next!=null)
        {
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode p=slow.next;
        slow.next=null;
        ListNode l1=sort(left,slow);
        ListNode l2=sort(p,right);
        return merge(l1,l2);
    }
    public ListNode merge(ListNode p,ListNode q)
    {
        ListNode phead=new ListNode(0),tail=phead;
        while(p!=null&&q!=null)
        {
            if(p.val<q.val)
            {
                tail.next=p;
                tail=tail.next;
                p=p.next;
            }
            else
            {
                tail.next=q;
                tail=tail.next;
                q=q.next;
            }
        }
        if(p!=null) tail.next=p;
        if(q!=null) tail.next=q;
        return phead.next;
    }

2. 快排。注意这里链表的快排不同于顺序表的快排，不需要双指针，只需要从头遍历一次链表，把比划分点小的结点断开取出来存放在另一个链表里，最后让大链表插在小链表后面，得到的新链表中划分节点位置一定是正确的。注意别忘了和原先链表前驱后继连起来，否则会断链，这里phead是待排序链表的前驱。

 public ListNode sortList(ListNode head) {
            ListNode phead=new ListNode(-1,head),tail=phead;
            while(tail.next!=null) tail=tail.next;
            quicksort(phead,tail);
            return phead.next;
    }
    public void quicksort(ListNode phead,ListNode tail)
    {
        if(phead.next==tail||phead==tail)
        return;
        ListNode end=tail.next,p=phead.next;
        ListNode big=new ListNode(0),small=new ListNode(0),ph=big,ps=small;
        int pro=p.val;
        while(p!=end)
        {
            if(p.val>=pro)
            {
                ph.next=p;
                ph=ph.next;
                p=p.next;
            }
            else
            {
                ps.next=p;
                ps=ps.next;
                p=p.next;
            }
        }
        ps.next=big.next;
        phead.next=small.next;
        ph.next=end;
        if(ps==small)  ps=phead;  
        quicksort(phead,ps);
        quicksort(big.next,ph);
    }

3. 有一种不需要递归直接自底向上的归并排序，空间可以达到O(1)，大致思路是用一个slen来记录归并块的大小，每排序完一轮后slen=slen*2，最后一个归并块的大小可以小于slen。每轮排序中可以根据slen来找到要归并的两个块的首节点和尾结点，需要考虑的有以下几个点：

• 通过merge排序后，会发现得到的有序链表会从原先的链表断开，因此得到有序链表后要重新和原先链表连接上。可以这样设计，merge(ListNode pre,int slen)，其中传入的形参是两个相连块首节点的前驱结点pre，slen是块的大小，在merge排序前还要保存下相连块尾节点的后继。排序完后将有序链表和前驱后继连起来。然后merge返回有序链表的尾节点，作为下次归并排序的前驱。
• 外循环中，可以设一个计数器来记录第一个有序块的长度，退出外循环条件是这个有序块的长度等于原先链表的长度，这时候说明排序完毕。