LeetCode 148. 排序链表
📌 题目描述
题目级别：中等
给你链表的头结点head，请将其按升序排列并返回排序后的链表。
进阶：
你可以在O(NlogN)O(N \log N)O(NlogN)时间复杂度和常数级空间复杂度下，对链表进行排序吗？
- 示例 1:
输入：head = [4,2,1,3]
输出：[1,2,3,4]
💡 破题思路：归并排序 (Divide and Conquer)
要在O(NlogN)O(N \log N)O(NlogN)时间内完成排序，常见的算法有快速排序、堆排序和归并排序。
但在链表这种数据结构中，**归并排序（Merge Sort）**是绝对的王者。因为它可以在合并阶段直接通过修改指针来实现，不需要像数组那样开辟大量的临时拷贝空间。
本解法采用了**自顶向下（Top-down）**的递归归并排序，核心分为两大步：
1. 分（Divide）：快慢指针找中点
利用经典的快慢指针法把链表从中间一分为二。
⚠️ 极客避坑点：
找中点时，fast指针必须初始化为head->next！
如果fast初始化为head，在处理只有 2 个节点的链表时，slow会走到第 2 个节点。此时从中点断开，左边依然是 2 个节点，会导致递归陷入死循环，最终爆栈。让fast先走一步，可以确保在偶数节点时，slow准确停在左半部分的最后一个节点。
2. 合（Merge）：双指针合并有序链表
这部分逻辑完全等同于经典的题目《21. 合并两个有序链表》。
创建一个虚拟头节点dummy，然后比较左右两半链表的当前节点，谁小谁就接在dummy的后面，最后将剩余的尾巴接上即可。
💻 C++ 代码实现 (原汁原味作者版)
classSolution{public:ListNode*sortList(ListNode*head){// 递归终止条件：如果链表为空，或只有一个节点，天然是有序的，直接返回if(!head||!head->next){returnhead;}// 1. 快慢指针找中点ListNode*slow=head;// 重点细节：fast 先走一步，防止偶数节点时划分死循环ListNode*fast=head->next;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}// 2. 将链表从 slow 处断开，分为 [head, slow] 和 [slow->next, 尾] 两部分ListNode*second=slow->next;slow->next=nullptr;ListNode*first=head;// 3. 对左右两半分别进行深度优先递归排序first=sortList(first);second=sortList(second);// 4. 将两个排序好的单链表合并returnmergeList(first,second);}// 辅助函数：合并两个有序链表ListNode*mergeList(ListNode*left,ListNode*right){ListNode*dummy=newListNode(0);ListNode*cur=dummy;while(left&&right){if(left->val<right->val){cur->next=left;left=left->next;}else{cur->next=right;right=right->next;}cur=cur->next;}// 把未遍历完的剩余部分直接挂在末尾if(left)cur->next=left;elsecur->next=right;returndummy->next;}};
