题目简述：
给你链表的头结点
head，请将其按 升序 排列并返回 排序后的链表 。**进阶：**你可以在
O(n log n)时间复杂度和常数级空间复杂度下，对链表进行排序吗？
题目链接：148. 排序链表
如果不是刻意构造的数据，快速排序算法的平均时间复杂度为
静态数组不支持在
- 如果 i 指向的元素大于选取的 pivot 则与 gter 指向的元素交换，gter--，i 保持不变，下次仍对比索引 i 的位置，因为尚未对比被交换来的元素；
- 如果 i 指向的元素小于选取的 pivot 则与 less 指向的元素交换，less++，i++；
- 如果 i 指向的元素等于选取的 pivot，i++；
- 如果 i == gter，结束本次遍历，接着分别对小于区与大于区递归该过程。
递归结束条件：
- 如果在循环遍历开始前发现 high <= low 则说明该区间内至多存在一个元素，不需要再排序，应当提前结束本次递归，不再向下进行遍历和稍后的递归调用，而是直接向上返回本次递归调用，最终随着所有递归全部返回，结束整个算法。
这样经过一轮遍历后，less左侧的元素均小于pivot，gter右侧的元素均大于pivot。
链表不支持
具体来说，选择一个 pivot 节点暂时抽离出链表，由于链表不支持随机访问，因此 pivot 可以简单地就取当前表头（取中间节点的话，要在递归时插入而额外的逻辑并且需要做初始化，会麻烦一点）。遍历链表，值小于等于 pivot 者断开当前连接、置于最左侧，值大于 pivot 者断开当前连接、置于最右侧（左侧部分和右侧部分独立，不相连），这样经过一轮遍历，也能实现小于等于区和大于区的划分，于是继续对小于等于区和大于区递归调用，并在调用递归后拼接小于等于区、pivot 节点与大于区。
由于链表不支持随机访问，因此无法三向切分，所以我们只划分小于等于区和大于区，这样导致应付大量重复值时会花费更多时间。递归的终止条件设置为递归输入的链表至多只包含一个节点。
需要特别说明的是，链表的快速排序实现中递归函数应该返回两个值，一个为排序后的头节点，一个为排序后的尾节点。如果只返回尾节点，连最终排序后的头节点都无法获取；如果只返回头节点，则无法连接小于等于区与 pivot，只能连接 pivot 与大于区。
总而言之，不论是数组还是链表，思路上都是一样的，本质上都是分治算法。如果没做额外要求，更推荐其他排序算法，例如归并排序甚至利用优先队列模拟最小堆排序（相比起直接转为数组排序后再转为链表，优先队列起码看起来优雅不少吧……），因为快速排序是不稳定的排序算法，面对被专门构造的数据时容易超时。
以下为使用快速排序实现的代码。
这份代码我没有优化 pivot 的选取，因此对刻意安排的数据时间复杂度容易退化为最坏情况
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
return quickSort(head)[0];
}
/**
* 返回头节点与尾节点数组
*/
public ListNode[] quickSort(ListNode head) {
if (head == null || head.next == null) return new ListNode[]{head, head};
ListNode pivot = head;
head = head.next;
ListNode lessHead = new ListNode(0, null), gterHead = new ListNode(0, null);
ListNode lessNode = lessHead, gterNode = gterHead;
while (head != null) {
if (head.val <= pivot.val) {
lessNode.next = head;
lessNode = head;
} else {
gterNode.next = head;
gterNode = head;
}
head = head.next;
}
lessNode.next = null;
gterNode.next = null;
ListNode[] less = quickSort(lessHead.next);
ListNode[] gter = quickSort(gterHead.next);
if(less[1] != null) less[1].next = pivot;
pivot.next = gter[0];
// 这个地方 debug 了好久才找出来并改正，太容易被忽视了
return new ListNode[]{less[0] == null? pivot : less[0], gter[1] == null? pivot : gter[1]};
}
}一共有30个测试用例，通过了前27个测试，在第28个测试中超时。第28个测试是从50000开始逐个递减直到1，就像专门针对快速排序一样，这种情况下时间复杂度为
归并排序分为从上至下的递归归并排序与自底向上的非递归归并排序。
两者时间复杂度均为稳定的
自底向上的递归归并思想十分简单，就是首先实现两个有序链表的排序（21. 合并两个有序链表），然后简单地应用分治算法归并地对子链表进行排序。
光是debug就折腾了好久。。。链表真麻烦。
class Solution {
/**
* 先不断切分，不可再切分后逐个升序合并
*
* @param head 输入链表头节点
* @return 返回升序排序后链表的头节点
*/
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode[] nodes = cutout(head);
nodes[0] = sortList(nodes[0]);
nodes[1] = sortList(nodes[1]);
return mergeTwoLists(nodes[0], nodes[1]);
}
/**
* 合并两个升序链表
*
* @param h1 输入升序链表头节点
* @param h2 输入升序链表头节点
* @return 返回合并后的新升序链表头节点
*/
public ListNode mergeTwoLists(ListNode h1, ListNode h2) {
if (h1 == null) return h2;
if (h2 == null) return h1;
ListNode dummy = new ListNode(0);
ListNode n = dummy;
while (h1 != null && h2 != null) {
if (h1.val < h2.val) {
n.next = h1;
h1 = h1.next;
} else {
n.next = h2;
h2 = h2.next;
}
n = n.next;
}
if (h1 != null) n.next = h1;
if (h2 != null) n.next = h2;
return dummy.next;
}
/**
* 利用快慢指针切分链表，找到终点并断开连接以便 sortTwoLists 合并排序
*
* @param h 输入链表头节点
* @return 返回 new ListNode[2]，其中 ListNode[0] 是左半部分头节点，ListNode[1] 是右半部分头节点
*/
public ListNode[] cutout(ListNode h) {
if (h == null || h.next == null) return new ListNode[]{h, null};
// if (h.next.next == null) return new ListNode[]{h, h.next};
ListNode fast = h;
ListNode slow = h;
ListNode slowPrev = null;
while (fast != null && fast.next != null) {
slowPrev = slow;
slow = slow.next;
fast = fast.next.next;
}
slowPrev.next = null;
return new ListNode[]{h, slow};
}
}真的夸张，被注释掉的那句 if (h.next.next == null) return new ListNode[]{h, h.next}; 能导致 sortList() 无限递归进而栈溢出，排查了一个小时才找出来问题。链表我*****
if (h.next.next == null) 本身没有问题，是可以单独处理这种情况的，问题在于直接 return new ListNode[]{h, h.next};，忘记了先断开连接……唉，给我干沉默了，一个小疏忽浪费一个小时时光。
这里的 cutout 最好是烂熟于心，一定记得用一个 slow 的前驱指针 prev 来断开连接，这会方便不少，避免了繁杂的逻辑处理。
整体思路和从上至下递归归并是一样的，也是利用合并两个有序链表 mergeTwoLists，但是方向相反，而且不用递归了只会更更更麻烦，要处理的点更更更多。。。。。。
先不写了，累了，倦了，麻了。贴一个AI的写的实现吧，我不想写了。以后有空回头二刷再研究吧。
这部分是AI写的
// 1. 计算链表长度 int length = 0; ListNode node = head; while (node != null) { length++; node = node.next; } ListNode dummy = new ListNode(0); dummy.next = head; // 2. 自底向上归并：块大小从1开始，逐步翻倍 for (int blockSize = 1; blockSize < length; blockSize *= 2) { ListNode prev = dummy; // 用于连接合并后的链表 ListNode curr = dummy.next; // 当前处理的节点 while (curr != null) { // 2.1 分割左块（大小为 blockSize） ListNode left = curr; ListNode leftEnd = split(left, blockSize); // 2.2 分割右块（大小为 blockSize） ListNode right = (leftEnd != null) ? leftEnd.next : null; if (leftEnd != null) leftEnd.next = null; // 断开左块 ListNode rightEnd = split(right, blockSize); ListNode next = (rightEnd != null) ? rightEnd.next : null; if (rightEnd != null) rightEnd.next = null; // 断开右块 // 2.3 合并左右块 ListNode merged = mergeTwoLists(left, right); prev.next = merged; // 将合并后的链表接回 // 2.4 移动 prev 到合并后的链表末尾 while (prev.next != null) { prev = prev.next; } // 2.5 处理下一组块 curr = next; } } return dummy.next;
这些办法虽然不会超时，效率也不低，但空间复杂度一般都在
比起直接转成数组然后 Arrays.sort()，利用优先队列进行最小堆排序起码要体面一点。嗯，也只是表面上的一点点体面了。
class Solution {
public ListNode sortList(ListNode head) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
ListNode cur = head;
int i;
for (i = 0; cur != null; cur = cur.next) { pq.offer(cur.val); i++; }
cur = head;
for (int j = 0; cur != null; cur = cur.next) { cur.val = pq.poll(); j++; }
return head;
}
}这就没什么好谈的了，转成数组，排序后再转回链表。数组的快速排序可以三向切分，可以方便地随机选取 pivot，效率极高。
class Solution {
public ListNode sortList(ListNode head) {
int[] arr = new int[50000];
ListNode cur = head;
int i;
for (i = 0; cur != null; cur = cur.next) { arr[i] = cur.val; i++; }
Arrays.sort(arr, 0, i);
cur = head;
for (int j = 0; cur != null; cur = cur.next) { cur.val = arr[j]; j++; }
return head;
}
}这个结果我是真绷不住了……那研究链表原生排序的意义在哪呢我请问了？
我知道这样子肯定不行，但我也是真绷不住。