借问江潮与海水
何似君情与妾心
C++，链表+排序，非递归，时间O(nlogn)，空间O(1)。
这里使用归并排序的非递归版本实现，说实话leetcode的medium很少有写这么长的。
其实就是归并排序，然后对链表进行排序的话，自然而然的会想到用非递归。
归并排序对于数组而言，是需要借助O(n)的辅助空间的，因为合并两个数组的时候需要储存中间结果，就会用到临时数组。
但是对于链表就不一样了，本来就是不连续空间，直接改变指针指向就好了。
思路其实也很简单，按照下面的思路来就行：
- 首先遍历链表得到链表总长度
len - 然后考虑使用归并的思想，对链表元素进行分组，然后对相邻链表
- 分组长度为1，分为
len个组，从前往后每两个相邻组的链表进行有序合并 - 分组长度为2，分为
len / 2 (+1)个组，从前往后每两个相邻组的链表进行有序合并 - 分组长度为4，分为
len / 4 (+1)个组，从前往后每两个相邻组的链表进行有序合并 - 分组长度为
2 * i，… - …
- 直到分组长度大于
len，这个时候就可以直接退出循环了
- 分组长度为1，分为
- 以上2的过程可以肯定的是，随着分组长度增大，每个分组都是有序的，当分组长度大于
len的时候，就全部有序了 - 需要注意的是：
- 合并两个链表的时候，因为每个链表的头尾会变，需要对边界的
next进行维护 - 可能存在分组的时候分成了奇数个组，进行合并的时候，最后会只剩只有一个分组，这最后的分组就只能和空指针
nullptr合并了 - 有可能在最后的时候，剩下的元素个数不足一个分组，这个时候注意不要段错误了。。。
- 链表这种题，用一个dummy前置结点简直是方便太多了呀！！！
- 合并两个链表的时候，因为每个链表的头尾会变，需要对边界的
这样就只会借助固定个数的辅助指针，所以空间复杂度为O(n)。
思路就是上面说的，代码如下：
/**
* 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 head;
int len = 0;
ListNode *p = head;
shared_ptr<ListNode> dummy = make_shared<ListNode>(-1);
ListNode *curr = nullptr;
dummy->next = head;
while (p) {
p = p->next;
len++;
}
for (int i = 1; i < len; i *= 2) {
p = dummy->next;
curr = dummy.get();
ListNode *left1 = nullptr, *left2 = nullptr;
ListNode *right1 = nullptr, *right2 = nullptr;
int cnt = 0;
for (int j = 0; j < len; j++) {
if (cnt == 0) left1 = p;
if (cnt == i - 1) right1 = p;
if (cnt == i) left2 = p;
if (cnt == i * 2 - 1 || p->next == nullptr) {
right2 = p;
p = right2->next;
if (left2) {
right1->next = nullptr;
right2->next = nullptr;
curr->next = merge(left1, left2);
}
else curr->next = merge(left1, nullptr);
cnt = 0;
while (curr->next) curr = curr->next;
left1 = left2 = right1 = right2 = nullptr;
continue;
}
p = p->next;
cnt++;
}
}
return dummy->next;
}
ListNode *merge(ListNode *l1, ListNode *l2) {
if (l2 == nullptr) return l1;
if (l1 == nullptr) return l2;
ListNode *dummy = new ListNode(-1);
ListNode *curr = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
curr->next = l1;
l1 = l1->next;
} else {
curr->next = l2;
l2 = l2->next;
}
curr = curr->next;
}
if (l1) curr->next = l1;
if (l2) curr->next = l2;
return dummy->next;
}
};
