LeetCode 148 排序链表解析：高效归并排序实现

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

输入：head = [4,2,1,3]
输出：[1,2,3,4]

代码解析

java

class Solution {public ListNode sortList(ListNode head) {// 递归终止条件：链表为空或只有一个节点if (head == null || head.next == null) {return head;}// 1. 获取链表中点ListNode mid = getMid(head);// 2. 分割链表为两部分ListNode rightHead = mid.next;mid.next = null; // 断开左右链表连接// 3. 递归排序左右子链表ListNode left = sortList(head);ListNode right = sortList(rightHead);// 4. 合并两个已排序的子链表return mergeSort(left, right);}// 合并两个有序链表private ListNode mergeSort(ListNode l1, ListNode l2) {ListNode dummyHead = new ListNode(0); // 哑节点简化操作ListNode cur = dummyHead;// 比较节点值，按升序连接while (l1 != null && l2 != null) {if (l1.val < l2.val) {cur.next = l1;l1 = l1.next;} else {cur.next = l2;l2 = l2.next;}cur = cur.next;}// 连接剩余节点cur.next = (l1 != null) ? l1 : l2;return dummyHead.next;}// 使用快慢指针找到链表中点private ListNode getMid(ListNode head) {ListNode fast = head;ListNode slow = head;// 快指针移动两步，慢指针移动一步while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow; // 慢指针指向中点（偶数时偏左）}
}

关键步骤详解

1. 递归终止条件

   • 当链表为空 (head == null) 或只有一个节点 (head.next == null) 时，直接返回，无需排序。

2. 获取链表中点（getMid）

   • 快慢指针法：快指针每次移动两步，慢指针每次移动一步。

   • 当快指针到达末尾时，慢指针指向中点（链表长度为偶数时指向前半部分最后一个节点）。

3. 分割链表

   • 将链表从中点处断开：mid.next = null。

   • 左子链表范围：[head, mid]。

   • 右子链表范围：[mid.next, 末尾]。

4. 递归排序子链表

   • 分别对左右子链表递归调用 sortList，直到子链表满足终止条件。

5. 合并有序链表（mergeSort）

   • 创建哑节点 dummyHead 简化链表连接操作。

   • 比较两个链表的当前节点值，将较小者接入新链表。

   • 当一个链表遍历完成后，将另一个链表的剩余部分直接接入。

复杂度分析

• 时间复杂度：O(n log n)

  • 每次分割链表需 O(n) 时间（通过快慢指针找中点）。

  • 递归深度为 O(log n)，每层合并操作总时间复杂度为 O(n)。

• 空间复杂度：O(log n)

  • 递归调用栈的深度（非递归版本可优化至 O(1)）。

为什么选择归并排序？

1. 链表特性适配

   • 链表节点不支持随机访问（无法高效实现快速排序的分区）。

   • 归并排序的合并操作只需改变指针，无需额外空间（数组归并需 O(n) 空间）。

2. 稳定性

   • 归并排序是稳定排序，保持相等元素的原始顺序。

总结

该解法利用分治思想，通过递归将链表不断分割、排序再合并，高效实现了 O(n log n) 的排序。快慢指针找中点与哑节点简化合并操作是处理链表问题的经典技巧。归并排序因其稳定性和适配链表结构的特性，成为解决此类问题的首选方案。