题目描述

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

进阶：

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

样例

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

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]

提示：
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
通过次数153,418提交次数228,204

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法1

(迭代方式的归并排序) 需要迭代log(n)次，每次归并遍历n，时间复杂度 $O(nlog(n))$

每次枚举 长度为i的数据，1，2，4，8…
每次归并长度为 2i的数据，2,4,8,16…
归并过程

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head) return head;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        int n = 0;
        while(head){
            ++n;
            head = head->next;
        } //计数n；

        //迭代归并排序
         //按照链表的长度枚举，排序
        for(int i = 1; i < n; i *= 2){ //枚举每次归并，两段中一段的长度，i <= n;也行
        //是因为，如果实际上i==n，说明i=n/2时，已经归并完成。
        //实际上i<n, i+1>n, 这个情况会使得l段1-i 和 r段i+1--结束归并。所以此处边界不用考虑
            auto cur = dummy;
            for(int j = 0; j + i < n; j += 2*i){  //j + i < n;j + i <= n 都可行。可以画1 2 3 例子理解。
//当j + i < n时，先归并1 和 2，3放到下一个循环中归并，作为r段的起点。
//j + i <= n时，先归并1 和 2，然后继续归并3，和最后的空指针。
                auto left = cur->next, right  = cur->next;
                for(int k = 0; k < i; ++k) right = right->next;  //找到归并右半段的起点
                int l = 0, r = 0;
                while(l < i && r < i && right){
                    if(left->val < right->val){
                        cur->next = left;
                        cur = left;
                        left = left->next;  ////必须要有这一步，因为要 遍历整个左半边的数
                        l++;
                    }
                    else{
                        cur->next = right;
                        cur = right;
                        right = right->next;
                        r++;
                    }
                }
// while(l < i && right){  //此处不能用right作为条件，因为当right这一段都 >
//左边这一段的时候，right已经到末尾了，right可能为nullprt。另外，right一定大于left。
//可是如果left先结束呢？这个情况怎么考虑？没有考虑测试也过了
//此处l 不会越界。j + i < n 保证一定会包含归并的l半段。

                while(l < i){
                    cur->next = left;
                    cur = left;
                    left = left->next;
                    l++;
                }
                while(r < i && right){
                    cur->next = right;
                    cur = right;
                    right = right->next;
                    r++;
                }
                cur->next = right;
            }
        }
        return dummy->next;
    }
};

//代码一样只是删除注释
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        int n = 0;
        while(head){
            ++n;
            head = head->next;
        }

        for(int i = 1; i <= n; i *= 2){
            auto cur = dummy;
            for(int j = 0; j + i <= n; j += 2 * i){
                auto left = cur->next, right = cur->next;
                for(int k = 0; k < i; ++k) right = right->next;
                //开始归并
                int l = 0, r = 0;
                while(l < i && r < i && right){
                    if(left->val < right->val){
                        cur->next = left;
                        cur = cur->next;
                        left = left->next;
                        ++l;
                    }
                    else{
                        cur->next = right;
                        cur = cur->next;
                        right = right->next;
                        ++r;
                    }
                } 
                while(l < i){
                    cur->next = left;
                    cur = cur->next;
                    left = left->next;
                    ++l;
                }
                while(r < i && right){
                    cur->next = right;
                    cur = cur->next;
                    right = right->next;
                    ++r;  
                }
                cur->next = right;
            }
        }
        return dummy->next;
    }
};