通知：吴师兄学算法训练营第十期开启报名，预计 12 月 20 开营，解锁 400 题。
一、题目描述
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
-
链表中节点的数目在范围 [0, 5 * 10^4]内 -
-10^5 <= Node.val <= 10^5
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
二、题目解析
我在这道题目的评论区看到有两个同学提到字节考察过，并且都是要实现 O(1) 的空间复杂度才过关。
“
这道题目确实挺有难度的，不画图，真的想不清楚。
”
题目要求时间空间复杂度分别为 O(nlogn) 和 O(1) ，根据时间复杂度和题目中的排序两个字，可以联想到归并排序和快速排序。
所以，本题有两种解法：归并排序和快速排序。
这里我们先用归并排序的思路进行处理，其中合并的基本操作如下：
-
1、长度为 1 的链表和长度为 1 的链表合并后，形成一个长度为 2 的链表 -
2、长度为 2 的链表和长度为 2 的链表合并后，形成一个长度为 4 的链表 -
。。。
而由于合并过程中操作的是链表，所以需要有断链和重新连接的过程。
具体操作步骤如下：
1、先获取链表长度，基于这个长度才能知道后续合并到什么时候截止
2、设置三个指针 prev、 curr、 next。
其中， prev表示已经排序好的链表的【尾节点】。
curr 一开始设置为准备排序的那些节点的【首节点】，然后向后移动，获取相应的节点，到达所有正在准备排序的那些节点的【尾节点】位置。
next 表示接下来需要排序的那些节点的【首节点】。
3、断开 prev 与 curr 的连接，再断开 curr 与 next 的连接。
4、把 curr 访问的这些节点划分为两个区域，区域的长度取决于此时进行到了长度为多少的链表进行合并操作，一个是左链表，一个是右链表，把这两个链表进行合并操作。
5、合并成功之后，prev 移动到尾部，curr 来到 next 的位置，继续后面的归并操作。
6、这样一轮下来，已经把长度为 2 的链表和长度为 2 的链表合并，形成了一个长度为 4 的链表。
7、接下来，只需要执行上述同样的操作，唯一的修改点在于合并的子链表长度变成了 4。
三、参考代码
// LeetCode 100 题精讲：https://mp.weixin.qq.com/s/yznC53g46phq3qF7V4-obA
// 作者：程序员吴师兄
// 排序链表（LeetCode 148）：https://leetcode.cn/problems/sort-list/
class Solution {
public ListNode sortList(ListNode head) {
// 获链表的总长度
int length = 0;
// 从链表的头节点开始访问
ListNode node = head;
// 利用 while 循环，可以统计出链表的节点个数，即长度
while (node != null) {
length++;
node = node.next;
}
// 在原链表的头部设置一个虚拟头节点
// 因为可能会操作到原链表的头节点
// 设置了虚拟头节点后，原链表的头节点和原链表的其它节点地位一样
ListNode dummyHead = new ListNode(0, head);
// 利用 for 循环，执行合并的操作
// 长度为 1 的链表和长度为 1 的链表合并后，形成一个长度为 2 的链表
// 长度为 2 的链表和长度为 2 的链表合并后，形成一个长度为 4 的链表
// 长度为 4 的链表和长度为 4 的链表合并后，形成一个长度为 8 的链表
// 长度为 8 的链表和长度为 8 的链表合并后，形成一个长度为 16 的链表
// 也有可能是，长度为 8 的链表和长度为 5 的链表合并后，形成一个长度为 13 的链表
// 但是，每次合并过程中，子链表都会想要扩充为原来的两倍
// 直到子链表想要扩充的长度超过了 length
for (int subLength = 1; subLength < length; subLength *= 2) {
// 整个归并过程分为三个步骤
// 1、不停的划分，直到无法划分为止
// 2、开始两两合并
// 3、每次合并之后的结果都需要连接起来
// 每次都把结果连接到 dummyHead，因此先记录一下
// prev 表示已经排序好的链表的【尾节点】
ListNode prev = dummyHead;
// dummyHead 的后面节点才是原链表的节点，需要把它们进行划分
// curr 表示所有正在准备排序的那些节点的【尾节点】
ListNode curr = dummyHead.next;
// 利用 while 循环，寻找出每次划分后子链表的头节点
while (curr != null) {
// 每次都是两个子链表开始合并
// 1、先寻找出【左子链表】，长度为 subLength
ListNode head1 = curr;
// 通过 for 循环，找出 subLength 个节点来
// curr 的索引为 0 ，需要再找 subLength - 1 个节点来
for (int i = 1; i < subLength && curr.next != null; i++) {
curr = curr.next;
}
// 2、再寻找出【右子链表】，长度最多为 subLength，甚至有可能长度为 0
ListNode head2 = curr.next;
// 此时，需要将【左子链表】与【右子链表】的连接断开
curr.next = null;
// curr 来到【右子链表】的头部
curr = head2;
// 通过 for 循环，找出【右子链表】的那些节点来
// 【右子链表】的节点个数可能达不到 subLength，甚至只有 1 个或者 0 个节点
for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
curr = curr.next;
}
// 获取到【右子链表】之后，需要把它和后续链表断开
// next 表示接下来需要排序的那些节点的【首节点】
ListNode next = null;
// 如果 curr != null，那么说明【右子链表】的节点个数达到了 subLength 个，并且后续还有节点
if (curr != null) {
// 记录一下后面节点
next = curr.next;
// 再将【右子链表】和后续链表断开
curr.next = null;
}
// 将【左子链表】与【右子链表】合并
ListNode merged = mergeTwoLists(head1, head2);
// 合并之后的结果需要连接到前一个链表
prev.next = merged;
// prev 来到链表的尾部，是下一个即将合成链表之后的前一个链表的尾节点
while (prev.next != null) {
prev = prev.next;
}
// curr 来到 next，处理后面的节点
curr = next;
}
}
return dummyHead.next;
}
// 合并两个有序链表的代码
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
ListNode dummy = new ListNode(-1);
// 设置一个指针，指向虚拟节点
ListNode pre = dummy;
// 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
while (l1 != null && l2 != null) {
// 如果 l1 当前节点的值小于等于了 l2 当前节点的值
if (l1.val <= l2.val) {
// 让 pre 指向节点的 next 指针指向这个更小值的节点
// 即指向 l1
pre.next = l1;
// 让 l1 向后移动
l1 = l1.next;
}else {
// 让 pre 指向节点的 next 指针指向这个更小值的节点
// 即指向 l2
pre.next =l2;
// 让 l2 向后移动
l2 = l2.next;
}
// 让 pre 向后移动
pre = pre.next;
}
// 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
// 直接把剩下的节点加入到 pre 的 next 指针位置
// 如果 l1 中还有节点
if (l1 != null) {
// 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
pre.next = l1;
}
// 如果 l2 中还有节点
if (l2 != null) {
// 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
pre.next = l2;
}
// 最后返回虚拟节点的 next 指针
return dummy.next;
}
}
玩转 LeetCode 高频 100 题系列正在更新，全系列题目和所有视频讲解可点击下方图片查看：
数组篇
链表篇
系列介绍：LeetCode 刷多少题能进大厂面试?
