(归并排序) 时间：O(nlogn)，空间O(1)
自顶向下递归形式的归并排序，由于递归需要使用系统栈，递归的最大深度是 logn，所以需要额外 O(logn)的空间。
所以我们需要使用自底向上非递归形式的归并排序算法。
基本思路是这样的，总共迭代 logn次：
第一次，将整个区间分成连续的若干段，每段长度是2：[a0,a1],[a2,a3],…[an?1,an?1]， 然后将每一段内排好序，小数在前，大数在后；
第二次，将整个区间分成连续的若干段，每段长度是4：[a0,…,a3],[a4,…,a7],…[an?4,…,an?1]，然后将每一段内排好序，这次排序可以利用之前的结果，相当于将左右两个有序的半区间合并，可以通过一次线性扫描来完成；
依此类推，直到每段小区间的长度大于等于 n?为止；
另外，当 n 不是2的整次幂时，每次迭代只有最后一个区间会比较特殊，长度会小一些，遍历到指针为空时需要提前结束。
时间复杂度分析：整个链表总共遍历 logn 次，每次遍历的复杂度是 O(n)，所以总时间复杂度是 O(nlogn)。
空间复杂度分析：整个算法没有递归，迭代时只会使用常数个额外变量，所以额外空间复杂度是 O(1)$.
/**
* 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) {
//利用自底向上的归并思想，可实现时间复杂度O(nlogn) 空间复杂度为O(1) 每次归并两小段 每小段的长度依次翻倍
//而使用自上向下的归并排序，时间复杂度为O(nlogn) 空间复杂度为O(logn)
int n = 0;
for (auto p = head; p; p = p -> next) n ++; //求出有链表有多少个节点
auto dummy = new ListNode(0); //设置一个哨兵节点
dummy -> next = head;
for (int i = 1; i < n; i *= 2){ //每次归并的长度，长度依次为1,2,4，8，，n/2,每次归并两小段
auto cur = dummy;
//j为二路归并第一段的起点，下一次归并起点要加二路归并的长度2i
for (int j = 1; j + i <= n; j += 2*i){
auto p = cur -> next, q = p; //p,q分别为指向二路归并中第一段、第二段的指针
for (int k = 0; k < i; k ++) q = q -> next; //寻找二路归并第二段起点
int x = 0, y = 0; //x、y分别用来计数当前第一段、第二段已经插入到链表cur的结点数，不应超过每段长度i
//在不超过每段长度i的前提条件下，每段链表的长度非2的整数倍时可能会小于i，因此要加上p,q的边界条件
while (x < i && y < i && p && q) {
//将每段中较小的值插入到链表cur中 其中<=号是为了保证归并排序为稳定的排序+
if (p->val <= q->val) cur = cur->next = p, p = p->next, x ++ ;
else cur = cur->next = q, q = q->next, y ++ ;
}
//归并的基本套路，要将剩下的链表插入到链表cur
while (x < i && p) cur = cur->next = p, p = p->next, x ++ ;
while (y < i && q) cur = cur->next = q, q = q->next, y ++ ;
//每次归并结束后，将链表cur的表尾指向下一次二路归并的表头，归并完成后q指向的是下一次归并的表头
cur->next = q;
}
}
return dummy -> next;
}
};?其中这题思想可回溯到ACwing算法基础课中的归并排序，该题思想是自顶向下的思想，由于在此过程中使用了递归，空间复杂度发生了变化，时间：O(nlogn)，空间O(logn)
另外可回顾个排序算法的时间复杂度和空间复杂度
?花花酱的代码参考代码