LeetCode148：排序链表(SortLinkedList)

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

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

---

题解与思路分析

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

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

以下是几种常见解法：

---

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

归并排序依赖“分治”：

分割链表：通过快慢指针找到链表的中点，将链表分成左右两半。递归排序左右子链表。合并两个有序链表：通过双指针合并两个递归排序后的链表。 模板代码（递归归并） 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; } } 时间和空间复杂度： 时间复杂度：O(n log n) 找中点需要 O(n)，递归二分对数级叠加，总时间复杂度为 O(n log n)。 空间复杂度：O(log n) 递归深度为 log n（由二分决定）。

---

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

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

从链表的最小子链表开始，每次合并两个子链表，逐步扩大子链表长度直到覆盖整个链表。使用一个内部循环控制子链表长度，外部循环控制链表的分组。 模板代码（迭代归并） 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; } } 时间和空间复杂度： 时间复杂度：O(n log n) 外循环处理 log n 层，每层最多 O(n)。 空间复杂度：O(1) 这种方法没有递归，因此是真正的原地排序。

---

解法 3：链表快速排序 思路

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

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

模板实现

class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; // 选择第一个节点作为 pivot ListNode 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 和 high ListNode sortedLow = sortList(lowHead.next); ListNode sortedHigh = sortList(highHead.next); // 拼接：low -> pivot -> high return 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; } } 时间和空间复杂度： 时间复杂度：O(n log n) 平均效率较高，最差 O(n²)。 空间复杂度：O(log n) 递归栈消耗。

---

经典变体题目 1. 合并 K 个有序链表（LeetCode 23）

解题方法：

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

---

2. 排序奇数链表部分

问题：

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

---

3. 重新排序链表

问题：

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

---

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