from CodeTop, Leetcode, 148. 排序链表。
迭代归并。
题意：
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
解读：
要求时间复杂度 O(nlogn) 自然而然就想到了快排和归并。但是快排，需要找随机节点，链表没有下标很难操作，于是归并。要求空间复杂度 O(1)，于是不能使用递归，要使用迭代。使用迭代，反而好做了。
- 首先，头结点不一定是最小的，可能会变动，那这种情况下就需要一个虚拟头结点，其 next 指针指向真正的头结点，这样无论真正的头结点怎样变化，我只需要返回虚拟头的 next 即可。
- 自底向上两两归并，设每次两两合并的段的长度为 i，则 i = 1 开始，每次变化到原来的两倍，直到
i >= n，说明当前两两合并的段的长度已经等于或超过了总的链表长度，也即，整个链表合并完成。 - 每一轮（基本段长度相等的，称为一轮）的合并，每一对两两相邻的段合并结束后，其头结点也可能变化，于是也需要使用一个虚拟头结点，其 next 指针指向真正的头结点。这个虚拟头结点会随着每两两合并的段的后移而后移，且始终其 next 节点指向当前需要两两合并的段的头结点。
比如，cur 最初等于虚拟头结点，指向 1,2 段的头节点（也就是 1 的头）。当第 1, 2 段完成合并后，cur 应当在完成合并的1,2 段的末尾，并且其 next 指针指向 3,4 段的头（也即是 3 的头）。 - 在每一轮（基本段长度相等的，称为一轮）的合并中，可能有不止一对两两相邻的段需要被合并。设起点（也就是相邻两段的第一段的起点）为 j，显然起点每次应当后移 2*i ，走到下一个需要两两合并的段的头结点位置。直到 j + i 大于 n (j 从零开始，j + i 大于 n 代表着当前段在段长度为 i 的情况下已经是孤零零一段，后面没有段可以合并了)。
当然，j 的作用，也仅限于计数计长度。 - 新建两个指针 first, second 指向两个段的头结点，新建两个变量 f, s 代表两个指针走了多少步（从零开始），开始归并：
- 显然，两两合并可进行的条件是指针都存在，且两个指针走的步数都小于 i。
- 两个指针指向相邻两段的节点，选取值较小的节点接到 cur 后面，相应的指针后移一位，步数加一。
- 两两合并后，应当由一个指针没有走完相应步数，不管具体是哪个指针，两个 while 收个尾，将未走完相应步数的一段接到 cur 后面。
- 结束，cur 指针应当指向合并段的最后节点，那么显然还应当使其 next 指向后面两段的头；后面两段的头，显然被 second 指向。于是 cur -> next = second。
代码及详细注释：
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (!head || !head -> next) return head;
//每次先归并好其中一小段，之后对两小段之间进行归并
int n = 0;
for(auto p = head; p ; p = p->next) n ++;
ListNode* dummy = new ListNode(-1, head);
// 因为 head 可能会变，因为原始的 head->val 可能不是最小的，就会被移到后面
// 要明白下面第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链表中
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;
}
};
