题目描述：
给定一个单链表 head，将其按升序排序并返回排序后的链表。

• 输入条件： 链表长度不固定（可为空）。
• 需要在O(n log n)时间复杂度和O(1)空间复杂度下完成 原地排序（特别限制）。

---

题解与思路分析

排序链表的经典解法通常围绕归并排序，因为归并排序天然适合链表场景，具有以下特点：

1. 链表无法随机访问： 链表适合用归并排序，而不适用快排（链表快排虽然实现复杂，但可以尝试）。
2. 时间复杂度要求 O(n log n)：
   归并排序在时间复杂度上满足要求；另一种选择是基于堆的优先队列排序。

以下是几种常见解法：

---

解法 1：归并排序（递归实现，分治法）

思路

归并排序依赖“分治”：

1. 分割链表：通过快慢指针找到链表的中点，将链表分成左右两半。
2. 递归排序左右子链表。
3. 合并两个有序链表：通过双指针合并两个递归排序后的链表。

模板代码（递归归并）

class Solution {public ListNode sortList(ListNode head) {// 递归结束条件：链表为空或只有一个节点if (head == null || head.next == null) {return head;}// 1. 找链表中点，拆分链表ListNode mid = findMiddle(head);ListNode rightHead = mid.next;mid.next = null; // 断开链表// 2. 递归排序左右两部分ListNode left = sortList(head);ListNode right = sortList(rightHead);// 3. 合并两个有序链表return mergeTwoLists(left, right);}// 快慢指针找链表的中点（慢指针指向下中点）private ListNode findMiddle(ListNode head) {ListNode slow = head, fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}// 合并两个有序链表private ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode p = dummy;while (l1 != null && l2 != null) {if (l1.val < l2.val) {p.next = l1;l1 = l1.next;} else {p.next = l2;l2 = l2.next;}p = p.next;}if (l1 != null) p.next = l1;if (l2 != null) p.next = l2;return dummy.next;}
}

时间和空间复杂度：

1. 时间复杂度：O(n log n)
   • 找中点需要 O(n)，递归二分对数级叠加，总时间复杂度为 O(n log n)。
2. 空间复杂度：O(log n)
   • 递归深度为 log n（由二分决定）。

---

解法 2：归并排序（迭代实现，自底向上）

思路

递归实现的归并排序需要调用栈导致 O(log n) 的空间复杂度，如果希望做到完全原地排序，可以使用迭代归并（Bottom-Up Merge Sort）：

1. 从链表的最小子链表开始，每次合并两个子链表，逐步扩大子链表长度直到覆盖整个链表。
2. 使用一个内部循环控制子链表长度，外部循环控制链表的分组。

模板代码（迭代归并）

class Solution {public ListNode sortList(ListNode head) {if (head == null || head.next == null) return head;// 1. 计算链表长度int length = 0;ListNode cur = head;while (cur != null) {length++;cur = cur.next;}// 2. Dummy 节点辅助处理ListNode dummy = new ListNode(0, head);// 3. 逐步扩大子链表长度 (size)for (int size = 1; size < length; size *= 2) {ListNode prev = dummy;  // 用于记录已处理部分尾节点cur = dummy.next;      // 当前未处理的链表头节点while (cur != null) {// 分割链表为 left 和 right 两部分ListNode left = cur;ListNode right = split(left, size); // 分割左链表，返回右链表的头cur = split(right, size);          // 分割右链表，返回下一部分的头// 合并两个有序链表prev.next = mergeTwoLists(left, right);// 移动到下一个部分末尾while (prev.next != null) {prev = prev.next;}}}return dummy.next;}// 按长度分割链表：截取链表前 size 个节点，返回剩余链表头private ListNode split(ListNode head, int size) {if (head == null) return null;ListNode cur = head;for (int i = 1; i < size && cur.next != null; i++) {cur = cur.next;}ListNode next = cur.next;cur.next = null; // 分割return next;}// 合并两个有序链表（同递归实现）private ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode p = dummy;while (l1 != null && l2 != null) {if (l1.val < l2.val) {p.next = l1;l1 = l1.next;} else {p.next = l2;l2 = l2.next;}p = p.next;}if (l1 != null) p.next = l1;if (l2 != null) p.next = l2;return dummy.next;}
}

时间和空间复杂度：

1. 时间复杂度：O(n log n)
   • 外循环处理 log n 层，每层最多 O(n)。
2. 空间复杂度：O(1)
   • 这种方法没有递归，因此是真正的原地排序。

---

解法 3：链表快速排序

思路

快速排序对链表不如数组好用，因为无法快速定位中点。实现上每次需要选取一个分区点 (pivot)，然后将链表分割为小于 pivot 和大于 pivot 的两部分，再递归排序。

1. 使用双链表法拆分：扫描每个节点，分为 low 和 high 列表。
2. 递归排序 low 和 high 后，拼接到 pivot。

模板实现

class Solution {public ListNode sortList(ListNode head) {if (head == null || head.next == null) return head;// 选择第一个节点作为 pivotListNode pivot = head;ListNode lowHead = new ListNode(0), highHead = new ListNode(0);ListNode low = lowHead, high = highHead;// 拆分链表ListNode cur = head.next;while (cur != null) {if (cur.val < pivot.val) {low.next = cur;low = low.next;} else {high.next = cur;high = high.next;}cur = cur.next;}low.next = null;high.next = null;// 递归排序 low 和 highListNode sortedLow = sortList(lowHead.next);ListNode sortedHigh = sortList(highHead.next);// 拼接：low -> pivot -> highreturn concat(sortedLow, pivot, sortedHigh);}private ListNode concat(ListNode low, ListNode pivot, ListNode high) {ListNode dummy = new ListNode(0), cur = dummy;cur.next = low;while (cur.next != null) cur = cur.next;cur.next = pivot;pivot.next = high;return dummy.next;}
}

时间和空间复杂度：

1. 时间复杂度：O(n log n)
   • 平均效率较高，最差 O(n²)。
2. 空间复杂度：O(log n)
   • 递归栈消耗。

---

经典变体题目

1. 合并 K 个有序链表（LeetCode 23）

解题方法：

• 分治合并：不断划分后两两合并链表。
• 优先队列：用小顶堆每次选择最小值。

---

2. 排序奇数链表部分

问题：

• 单链表中仅奇数值的节点需要排序，而偶数节点保持原顺序。
• 解法：拆分原链表，分别排序后再合并。

---

3. 重新排序链表

问题：

• 链表重新排序：head -> tail -> nextHead -> nextTail …
• 双指针中点拆分 + reverse 后半部分处理。

---

快速 AC 总结：

1. 优先熟练掌握 递归归并排序，作为 LeetCode AC 的首选。
2. 迭代归并排序在强调空间复杂度下非常重要。
3. 拓展常见链表排序变形，熟悉归并/快排的变体问题应对跨题目场景！