题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

样例

1、算法思路：

对链表进行排序且时间为O(n*logn)，首先想到的是递归的归并排序，但是递归有logn层，则空间复杂度为O(logn)，不符合题意。则这题我们采用 “自下向上的归并排序”；

1.1 自下向上的归并排序(枚举的思想)

用枚举来模拟整个归并的过程：

//首先枚举每个区间的长度，开始先合并长度为1的区间，后面是2....最后在长度大于等于n时候停止；
for(int i=1; i<n; i=i*2)
{
    //然后再逐一枚举前后两个区间，将其合并；
    for(int j=0; j+i<n; j+=2*i)
    {
        //归并排序细节
    }
}

2、c++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //考察知识点： 自下向上的归并排序
    ListNode* sortList(ListNode* head) {
        if(!head) return NULL;
        auto dummy = new ListNode(-1);
        dummy->next = head;

        //先求出链表的长度：
        int n = 0;
        for(auto p=head; p; p=p->next) n++;

        //然后先一小段的合并，再两倍的合并，一直到长度大于等于n时候截止：
        for(int i=1; i<n; i=i*2) //每次合并区间的长度，当合并区间大于等于n时候停止！！！
        {
            auto start = dummy; //每次都从头开始合并
            for(int j=0; j+i<n; j+=i*2) //总共区间的个数，每次将前后两个区间合并
            {
                auto left = start->next, right = start->next;
                for(int k=0; k<i; k++) right = right->next; //left为第一个区间的第一个节点， right为第二个区间的第一个节点

                int l = 0, r = 0;

                //将前后两个区间进行归并合并
                while(l < i && r < i && right) //这里为了防止最后一个区间长度小于i时，r越界，所以多加一个判断条件
                {
                    if(left->val <= right->val)
                    {
                        start->next = left;
                        start = left;
                        left = left->next;
                        l++;
                    }
                    else{
                        start->next = right;
                        start = right;
                        right = right->next;
                        r++;
                    }
                }

                while(l < i){
                    start->next = left;
                    start = left;
                    left = left->next;
                    l++;
                }

                while(r < i && right){
                    start->next = right;
                    start = right;
                    right = right->next;
                    r++;
                }

                //最后right是下一个区间的第一个位置，最后注意将start->next指向right
                start->next = right;
            }
        }

        return dummy->next;
    }
};