题目内容

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

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

提示

1、链表中节点的数目在范围 [0, 5 * 10^4] 内
2、-10^5 <= Node.val <= 10^5

题解

首先，题目要求使用O(n log n) 时间复杂度和O(1)的空间复杂度，因此在所有的排序算法中，只有归并排序并且按照迭代的要求进行才满足要求。

然后，思路如下：

第一次，将整个区间分成连续的若干段，每段长度是2：[a0,a1],[a2,a3],…[an−2,an−1]， 然后将每一段内排好序，小数在前，大数在后；
第二次，将整个区间分成连续的若干段，每段长度是4：[a0,…,a3],[a4,…,a7],…[an−4,…,an−1]，然后将每一段内排好序，这次排序可以利用之前的结果，相当于将左右两个有序的半区间合并，可以通过一次线性扫描来完成；
依此类推，直到每段小区间的长度大于等于 n 为止；

另外，当 n 不是2的整次幂时，每次迭代只有最后一个区间会比较特殊，长度会小一些，遍历到指针为空时需要提前结束。

代码

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        //利用自底向上的归并思想，每次先归并好其中一小段，之后对两小段之间进行归并
        int n = 0;
      //求出链表长度
        for(auto p = head; p ; p = p->next) n ++;
        auto dummy = new ListNode(-1); // 虚拟头结点用于指向每一层归并的最终排好序的链表，head在排序的过程中可能会变化，因此不能用head。
        dummy->next = head;
        // 要明白下面第1个和第2个for循环是什么，第1个for循环是纵向层与层之间的迭代，第2个for循环是横向每层从左往右每次2i段遍历
        for(int i = 1; i < n; i *= 2 ){ //每次归并段的长度，每次长度依次为1,2,4,8...n/2
        //小于n是因为等于n时说明所有元素均归并完毕，大于n时同理
            auto cur = dummy; // 因为下面for循环第一次进入时(即每一层第一段头结点 是从第一个结点head开始的，这个第一个结点head也是会变的)，要保证 first = head, 所以这里要将 cur = dummy, 因为dummy->next =head, 能保证 first = cur->next = head 
            // 根据把链表头结点 索引当成0 或 1 有两种写法：写法一： j = 0; j + i < n;     写法二：j = 1; j + i <= n;
            for(int j = 0; j + i < n; j += 2 * i){//j代表每一段的开始，每次将两段有序段归并为一个大的有序段，故而每次+2i
            //必须保证每段中间序号是小于链表长度的，显然，如果大于表长，就没有元素可以归并了
                auto first = cur->next, second = first;//p表示2i段第一段的起始点，cur是上一排好序的2i链表段的尾结点（这个起始点会变，不能用p=head），q表示2i段第二段的起始点，之后开始归并即可
                for(int k = 0; k < i; k ++) second = second->next;
                //f,s用于计数第一段和第二段归并的节点个数，由于当链表长度非2的整数倍时表长会小于i,故而需要加上first && second的边界判断
                 int f = 0, s = 0;
                 while(f < i && s < i && first && second){  // 加 && second 是因为 第二段长度 可能不满 i
                // 这里可以不用 && first, 因为上面 j+i<=n 保证了，有第二段，所以第一段肯定存在 且 长度为i
                     if(first->val <= second->val) cur = cur->next = first,first = first->next,f ++; //等号的赋值顺序为从右到左，故而该句意思为
                     //cur->next = first,cur = cur->next,即将小的一点插入cur链表中
                     // 此处注意 归并排序 用 数组是这种形式，tmp[k ++ ] = first[i ++ ]，但是这里不能采用cur = first, cur = cur->next,这样就不对了，这是 链表实现归并排序 与数组实现归并排序不同之处，要注意,可以写成cur->next = first ，cur = first 
                     else cur = cur->next = second,second = second->next,s++;
                 }
                //归并排序基本套路
                 while(f < i && first) cur = cur->next = first,first = first->next,f ++; // 这里可以不加 && first，原理同上
                 while(s < i && second) cur = cur->next = second,second = second->next,s ++;  // 跳出循环时，second已经是 j+2i 下一2i链表段的新的头结点
                 cur->next = second; //记得把排好序的链表尾 链接 到 j+2i 下一2i链表 的表头，循环完毕后 second 为下一2i链表表头
            }
        } 
        return dummy->next;
    }
};