题干
给你链表的头结点 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 * 104]内 -105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
思路
- 从链表中点处断开链表
- 递归左右链表，递归的返回值为排序之后的左链表与右链表
- 同时遍历左右链表，将左右链表重新排序成一个新链表
- 返回这个新链表
假设有一个数值为[5, 2, 1, 4, 3]的链表需要排序。每一个彩色框代表进入一次递归：
代码&gpt总结
这段代码实现了对链表的排序算法，采用了归并排序的思想。以下是对这段算法的详细分析：
-
算法逻辑
算法首先检查输入的链表头节点是否为空，如果为空，则直接返回
null。使用快慢指针方法找到链表中点，快指针每次移动两步，慢指针每次移动一步，当快指针无法继续前进时，慢指针所在的位置即为中点。这样，链表被分为左右两部分，分别对这两部分递归地进行排序。最后，使用归并的方式合并两个已排序的链表部分，得到完全排序后的链表。 -
变量解释
head: 输入的链表头节点。f(fast): 快指针，用于找到链表的中点。s(slow): 慢指针，随着快指针的移动而移动，当快指针到达链表末尾时，慢指针位于链表中点。l(left): 表示分割后的左半部分链表的头节点。r(right): 表示分割后的右半部分链表的头节点。dummyNewHead: 一个哑节点，用于辅助归并排序的过程。nowNode: 当前操作的节点，用于构建排序后的链表。
-
关键代码分析
while (f.next?.next): 快慢指针移动，直到快指针到达链表末尾或无法继续前进。s.next = null: 将链表从中点断开，分为左右两部分。- 递归调用
sortList(l)和sortList(r): 对左右两部分链表分别进行排序。 while (l && r): 归并排序的主要步骤，比较左右两部分链表的头节点，将较小的节点连接到结果链表上，直到一方为空。nowNode.next = l || r: 将剩余的非空链表部分连接到结果链表的尾部。
-
性能分析
- 时间复杂度：O(n log n)，其中n是链表的长度。归并排序的时间复杂度为O(log n)，对于每一层归并，需要遍历所有节点，故总的时间复杂度为O(n log n)。
- 空间复杂度：O(log n)，递归调用的栈空间。由于是使用递归实现的，空间复杂度主要由递归深度决定，即链表的分割次数，为O(log n)。
-
适用场景
- 对不支持随机访问的数据结构，如链表进行排序时，归并排序是非常合适的选择，因为它不依赖于随机访问。
- 在需要稳定排序算法的场景下，归并排序保持了相同元素之间的相对顺序，适用于此类需求。
- 当处理的数据量很大，且数据无法全部加载到内存中时，归并排序能够有效地分治处理，适合外部排序。
function sortList(head: ListNode | null): ListNode | null {
if (head === null) return null;
let f: ListNode | null = head;
let s: ListNode = head;
// 寻找链表中点
while (f.next?.next) {
f = f.next?.next ?? null;
s = s.next!;
if (!f?.next) break;
}
let l: ListNode | null = head;
let r = s.next;
// 断开链表
s.next = null;
// 左右链表递归的进行排序，返回排序完成的左右链表
if (l?.next) l = sortList(l);
if (r?.next) r = sortList(r);
const dummyNewHead = new ListNode(-1);
let nowNode = dummyNewHead;
// 遍历排序完成的左右链表，将两个链表合并成一个排序完成的链表
while (l && r) {
let nextNode = null;
if (l?.val < r?.val) {
nextNode = l;
l = l!.next ?? null;
} else {
nextNode = r;
r = r!.next ?? null;
}
nowNode.next = nextNode as ListNode;
nowNode = nowNode.next;
}
nowNode.next = l || r;
// 返回排序完成的链表
return dummyNewHead.next;
}