算法思考：单链表的快排与归并
前言
一直不敢写算法的文章，因为很容易被算法大佬打脸?。不过前两天遇到一个题，单向链表的高等排序，挺有意思。虽然这是基础题，但是对于理解快速排序和归并排序的原理有着很大作用。
本文主要讲解笔者处理该问题时的思考方式及思路，更多的是思维层面的东西。在 AC 之前笔者是没有看 Discuss 的，所涉及到的代码都有优化空间，也不是最优解，所以算法大佬们请手下留情?。
贴上 leetcode 的题 148. Sort List
sort list
排序算法的选择
题目要求 O(nlogn) 时间复杂度，意味着常用算法快排和归并都能纳入考虑范围。当笔者看到常数空间复杂度时，第一反应是排除归并算法，因为常规的数组的归并排序需要用 O(n) 的额外空间来提高时间效率，实际上单链表比较特殊，它的归并排序可以在保证时间效率的情况下在常数空间内完成，只是在处理上有一点复杂，后文会讲。综合考虑之下，似乎快排和归并都能砍下这道题。
尝试快排
快排是一个人气很高的算法，以其在通常情况下极高的效率著称，但是在处理相对有序的数据时时间复杂度最坏能退化到 O(n²) ，而为了避免这种情况，需要一些额外的技巧，减小分割时取值过于极端的情况发生。
快排和归并通常都是基于分治思想来做的，而提起分治就少不了递归，它能让代码更加易读和简洁。
那么，快排的核心问题就是如何分割，下面贴上笔者写的两个基于数组分割的代码。
常见的一种就是采用双边指针向中间扫：
int partitionB(int *a, int left, int right) {
int x = left, y = right, t = a[right];
while (x < y) {
while (x < y && a[x] <= t) ++x;
a[y] = a[x];
while (x < y && a[y] > t) --y;
a[x] = a[y];
}
a[y] = t;
return x;
}另外一种是用一个指针做间隔用，一个指针做遍历用：
int partitionA(int *a, int left, int right) {
int x = left-1, y = left;
for (; y < right; ++y) {
if (a[y] < a[right]) {
int tmp = a[y];
a[y] = a[++x];
a[x] = tmp;
}
}
int tmp = a[x+1];
a[x+1] = a[right];
a[right] = tmp;
return x+1;
}这里就不过多解释两种思路的原理，百度应该很容易找到科普文章。
现在重点来了，考虑单链表的特殊性，我们如何来选择分割方式？
方法一的思考
对于双边指针的方法，左指针会前进，右指针会回退，而当前的场景是单向链表，也就是只有 next 指向后驱元素的指针，而没有指向双亲的指针，这就给右指针的回退带来了困难。
方法二的思考
一个指针做间隔，一个指针做遍历，虽然同样是两个指针，但是它们都不用回退，只需要将遍历到的结点插入间隔指针的前（后）就行了。所以这里主要是涉及到一个单链表结点交换的算法。
贴上笔者实现的代码：
class Solution {
private:
void exchangeNodes(ListNode *xPre, ListNode *yPre) {
if (!xPre || !yPre) return;
ListNode *x = xPre->next, *y = yPre->next;
if (!x || !y || x == y) return;
if (x->next == y) {
ListNode *ySuf = y->next;
xPre->next = y;
y->next = x;
x->next = ySuf;
} else if (y->next == x) {
ListNode *xSuf = x->next;
yPre->next = x;
x->next = y;
y->next = xSuf;
} else {
ListNode *xSuf = x->next, *ySuf = y->next;
xPre->next = y;
yPre->next = x;
y->next = xSuf;
x->next = ySuf;
}
}
ListNode *partition(ListNode *head, ListNode *start, ListNode **end) {
ListNode *x = start, *y = start->next, *yPre = start;
while (y && y != *end) {
if (y->val < (*end)->val) {
exchangeNodes(x, yPre);
x = x->next;
}
yPre = y;
y = y->next;
}
exchangeNodes(x, yPre);
*end = yPre->next;
return x;
}
void quikSort(ListNode *head, ListNode *start, ListNode *end) {
if (!start || !end || start == end || start->next == end) return;
ListNode *tmp = partition(head, start, &end);
quikSort(head, start, tmp);
quikSort(head, tmp->next, end);
}
public:
ListNode* sortList(ListNode* head) {
if (!head) return head;
ListNode *root = (ListNode *)malloc(sizeof(ListNode));
root->next = head;
ListNode *foot = head;
while (foot->next) foot = foot->next;
quikSort(root, root, foot);
return root->next;
}
};如果大概看懂了的朋友应该发现了，核心算法中笔者没有做头结点的判断，该题提供的数据源也是没有头结点的。所以可以先加一个头结点，返回值的时候去掉就行了，因为我始终觉得一个好的链表要有一个头结点，这样方便各种操作逻辑的统一，而且链表的额外信息也可以记录在头结点中。
所以，完成了编码过后，笔者自信的点击了 submit solution，等待了几秒钟之后，尴尬的事情发生了：
通过了15个测试用例之后，最后一个超时了?。一看测试用例的数据，明显是快排的时间复杂度退化了。。。当然，这里可以考虑加上一些逻辑来降低这种极限情况的时间消耗，不过，为了代码的简洁，笔者决定采用归并来处理，也可以加深对分治法的理解。
尝试归并
归并算法分两个大步骤，一个是分割，一个是合并，正巧可以用栈来完美处理，即入栈的时候分割，出栈的时候合并。
如何处理分割？
在对于数组的处理中，是这样分割的：
void mergeSort(int *a, int left, int right) {
if (left + 1 >= right) return;
int mid = (left + right) / 2;
mergeSort(a, left, mid);
mergeSort(a, mid, right);
mergeA(a, left, mid, right);
}很简洁的代码，但是对于链表如何处理呢？单链表是没有 hash 特性的，怎么拿到多个结点的中间结点？
最容易想到是，先遍历一次记录所有结点的数量，再遍历第二次找到中间结点，嗯。。不得不说这样感觉很 low。
所以笔者检索了一下，看到有同僚使用快慢指针来处理，减少一些时间消耗，眼前一亮~
既一个慢指针走一步，一个快指针走两步，快指针走完，慢指针指向的位置就是中间结点（当然可能不是绝对的中间）。
如何处理合并？
笔者之前写的处理数组归并中的合并算法：
void mergeA(int *a, int left, int mid, int right) {
int n0 = mid - left, n1 = right - mid;
int tmpA[n0], tmpB[n1];
for (int i = 0; i < n0; ++i) tmpA[i] = a[i + left];
for (int i = 0; i < n1; ++i) tmpB[i] = a[i + mid];
int x = 0, y = 0;
for (int i = left; i <= right; ++i) {
if (x >= n0 && y >= n0) break;
if (y >= n1 || (x < n0 && tmpA[x] <= tmpB[y])) a[i] = tmpA[x++];
else a[i] = tmpB[y++];
}
}一看，O(n) 级别的空间消耗，这种做法肯定是不适合链表的。
所以，我们不如思考这样一个问题，上面利用额外的空间来合并是为了什么？想一想顺序存储结构线性表的特性，若不使用额外的空间，每次插值都意味着后续元素的位置移动，即 O(n) 的时间复杂度，这当然不可容忍。
那么，转念一想，我们的链式存储结构线性表的插入和删除不是 O(1) 的么？哈哈，所以完全不需要这么多空间，最多就几个指针就能实现链表的合并了，于是，笔者就开始撸码了。。
class Solution {
private:
void insertNode(ListNode **leftPre, ListNode *rightPre) {
ListNode *target = rightPre->next;
rightPre->next = target->next;
ListNode *sureSuf = (*leftPre)->next;
(*leftPre)->next = target;
target->next = sureSuf;
*leftPre = target;
}
ListNode* merge(ListNode *start, ListNode *mid, ListNode *end) {
ListNode *xPre = start, *yPre = mid, *end_next = end->next;
while (xPre != mid || yPre->next != end_next) {
if (xPre == mid) {
yPre = yPre->next;
} else if (yPre->next == end_next) {
xPre = xPre->next;
} else {
if (xPre->next->val <= yPre->next->val) {
xPre = xPre->next;
} else {
insertNode(&xPre, yPre);
}
}
}
return yPre;
}
ListNode* mergeSort(ListNode *start, ListNode *end) {
if (!start || !start->next || start->next == end) return end;
ListNode *low = start->next, *fast = start->next;
while (fast && fast->next && fast->next != end->next && fast->next->next && fast->next->next != end->next) {
low = low->next;
fast = fast->next->next;
}
ListNode *tmp_low = mergeSort(start, low);
ListNode *tmp_end = mergeSort(tmp_low, end);
return merge(start, tmp_low, tmp_end);
}
public:
ListNode* sortList(ListNode* head) {
if (!head) return head;
ListNode *root = (ListNode *)malloc(sizeof(ListNode));
root->next = head;
ListNode *foot = head;
while (foot->next) foot = foot->next;
mergeSort(root, foot);
return root->next;
}
};一提交，看到了漂亮的图案：
值得注意的是，链表的归并算法的细节处理比较复杂，要考虑的是何时插值，最容易忽略的地方就是，在插值的过程中，可能尾结点 end 的位置被交换了，所以可以看到笔者的合并方法中返回了一个 yPre， 它最后会指向排序后的尾结点。
写在后面
链表看起来很简单的结构，实际上有着不少的学问，特别是边界处理和增删改查，在处理本文所述问题中，笔者经常使用前驱结点来做目标结点的逻辑，这样就不用额外的指针来保持前驱结点了。
算法确实是有意思的东西，它不仅能很大程度的提高一个人的思维，还能让你在思考问题写业务的时候也能从多个角度思考问题，而不是片面的解决了问题不知如何优化而不了了之。
腾讯云开发者
