4. 時(shí)間復(fù)雜度是O(nlogn)，空間復(fù)雜度是O(logn)，即遞歸調(diào)用的深度

public class Solution {
    public ListNode SortList(ListNode head) {
        if(head==null || head.next==null) return head;
        var secondHead = Split(head);
        head=SortList(head);
        secondHead=SortList(secondHead);
        return Merge(head,secondHead);
    }
    ListNode Merge(ListNode head1, ListNode head2)
    {
        var dummy=new ListNode(0);
        var cur=dummy;
        while(head1!=null&&head2!=null)
        {
            if(head1.val<=head2.val)
            {
                cur.next=head1;
                head1=head1.next;
            }
            else
            {
                cur.next=head2;
                head2=head2.next;
            }
            cur=cur.next;
        }
        if(head1!=null) cur.next=head1;
        else cur.next=head2;
        return dummy.next;
    }
    ListNode Split(ListNode head)
    {
        ListNode slow=head, fast=head.next;
        while(fast!=null&&fast.next!=null)
        {
            slow=slow.next;
            fast=fast.next.next;
        }
        var newHead = slow.next;
        slow.next=null;
        return newHead;
    }
}

空間復(fù)雜度再降低-自底向上的歸并

1. 熟悉歸并排序的兄弟應(yīng)該知道，若采用自下而上的歸并，可以把遞歸調(diào)用改為迭代的，不使用額外空間

2. 但是對(duì)于鏈表來(lái)講，可以把只有1個(gè)節(jié)點(diǎn)的鏈表看成有序的，即歸并的底

3. 兩個(gè)長(zhǎng)度為1的鏈表合并為長(zhǎng)度為2的有序鏈表，那么兩個(gè)長(zhǎng)度為2的鏈表合并為長(zhǎng)度為4的有序鏈表，以此類(lèi)推

4. 現(xiàn)在我們?cè)O(shè)歸并長(zhǎng)度是len，當(dāng)然一開(kāi)始len=1，每進(jìn)行一輪歸并，len*=2，當(dāng)len>=原始鏈表長(zhǎng)度的時(shí)候，鏈表的排序就完成了

我們曉得鏈表始終不能斷開(kāi)的，所以merge方法中不能用null來(lái)判斷是否合并完一條鏈表

我們把merge方法設(shè)計(jì)成

void Merge(ListNode beforeHead, ListNode mid, ListNode afterTail)

• beforehead用于確定head1和合并的指針的位置
• mid是鏈表2的開(kāi)始head2(頭結(jié)點(diǎn)），同時(shí)也是鏈表1的結(jié)尾哨兵
• afterTail是鏈表2的結(jié)尾哨兵

那如何確定每次合并的3個(gè)參數(shù)？

• 對(duì)每個(gè)len的首次合并，beforeHead為鏈表頭部之前的哨兵節(jié)點(diǎn)
• mid為beforeHead后面的第len+1個(gè)節(jié)點(diǎn)
• afterTail為mid后面的第len個(gè)節(jié)點(diǎn)
• 使用上述參數(shù)完成一個(gè)區(qū)間的合并
• 下一個(gè)區(qū)間的beforeHead為beforeHead后面的第len*2個(gè)節(jié)點(diǎn)
• 以上移動(dòng)均需注意是否達(dá)到鏈表尾部的null
• 若beforeHead為null，本輪合并完成

時(shí)間復(fù)雜度是O(nlogn)，空間復(fù)雜度是O(1)，只使用了幾個(gè)變量和1層函數(shù)調(diào)用

//c#的代碼  
public class Solution {
    public ListNode SortList(ListNode head) {
        if(head==null||head.next==null) return head;
        int n=0;
        ListNode dummy = new ListNode();
        dummy.next=head;
        var cur = head;
        while(cur!=null)
        {
            cur=cur.next;
            n++;
        }
        int len=1;
        while(len<n)
        {
            var beforeHead=dummy;
            while(beforeHead!=null)
            {
                var mid = beforeHead.next;
                for(int i=0;i<len;i++)
                {
                    if(mid!=null) mid=mid.next;
                    else break;
                }
                var afterTail=mid;
                for(int i=0;i<len;i++)
                {
                    if(afterTail!=null) afterTail=afterTail.next;
                    else break;
                }
                Merge(beforeHead,mid,afterTail);
                for(int i=0;i<len*2;i++)
                {
                    if(beforeHead!=null)
                        beforeHead=beforeHead.next;
                    else break;
                }
            }
            len*=2;
        }
        return dummy.next;
    }
    void Merge(ListNode beforeHead, ListNode mid, ListNode afterTail)
    {
        var cur = beforeHead;
        var head1 = cur.next;
        var head2 = mid;
        while(head1!=mid&&head2!=afterTail)
        {
            if(head1.val<=head2.val)
            {
                cur.next=head1;
                head1=head1.next;
            }
            else
            {
                cur.next=head2;
                head2=head2.next;
            }
            cur=cur.next;
        }
        while(head1!=mid)
        {
            cur.next=head1;
            head1=head1.next;
            cur=cur.next;
        }
        while(head2!=afterTail)
        {
            cur.next=head2;
            head2=head2.next;
            cur=cur.next;
        }
        cur.next=afterTail;
    }
}