148. 排序链表

148. 排序链表

中等

给你链表的头结点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)时间复杂度和常数级空间复杂度下，对链表进行排序吗？

📝 核心笔记：排序链表 (Sort List)

1. 核心思想 (一句话总结)

“分而治之：先把长链表切成两半，分别排好序，再把两条有序链表拉链式合并。”

这是LC 21 (合并两个有序链表)和LC 876 (链表的中间结点)的集大成者。

• 分 (Divide)：利用快慢指针找到中点，将链表断开成两条。
• 治 (Conquer)：递归地对这两条子链表进行排序。
• 合 (Combine)：将排好序的子链表合并（归并）。

2. 算法流程 (递归三步曲)

1. 找中点并断链 (middleNode)：

• • 使用快慢指针。
  • 关键点：必须记录slow的前驱节点pre。找到中点后，执行pre.next = null。
  • 如果不切断，链表还是连在一起的，递归就会陷入死循环 (StackOverflow)。

1. 递归排序 (sortList)：

• • 对左半部分 (head) 递归。
  • 对右半部分 (head2) 递归。
  • 基准条件：如果链表为空或只有一个节点，直接返回。

1. 合并 (mergeTwoLists)：

• • 将两个有序链表合并为一个（直接复用之前的逻辑）。

🔍 代码回忆清单

// 题目：LC 148. Sort List class Solution { public ListNode sortList(ListNode head) { // 1. 递归终止条件 (Base Case) // 0 个或 1 个节点本身就是有序的 if (head == null || head.next == null) { return head; } // 2. 找中点并【切断】 // 这里复用了"寻找中点"的逻辑，但多了一步"切断" ListNode head2 = middleNode(head); // 3. 分治 (Divide) head = sortList(head); // 排序前半段 head2 = sortList(head2); // 排序后半段 // 4. 合并 (Combine) // 复用合并有序链表的逻辑 return mergeTwoLists(head, head2); } // 辅助 1: 找中点 + 断链 private ListNode middleNode(ListNode head) { ListNode pre = head; // 用于断后路 ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { pre = slow; // pre 紧跟 slow 后面 slow = slow.next; fast = fast.next.next; } // 核心操作：把链表一分为二 // 此时 head~pre 是前半段，slow~end 是后半段 pre.next = null; return slow; // 返回后半段的头 } // 辅助 2: 合并有序链表 (标准的 LC 21) private ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(); ListNode cur = dummy; while (list1 != null && list2 != null) { if (list1.val < list2.val) { cur.next = list1; list1 = list1.next; } else { cur.next = list2; list2 = list2.next; } cur = cur.next; } cur.next = list1 != null ? list1 : list2; return dummy.next; } }

⚡ 快速复习 CheckList (易错点 & 进阶)

• [ ]为什么必须用pre.next = null？

• • 面试高频点。这是链表归并排序和数组归并排序最大的不同。数组是通过下标计算划分区域的，物理上不用切断；链表是通过指针连接的，如果不物理切断，head顺着走还能走到head2，逻辑就乱了，且会导致无限递归。

🖼️ 数字演练

链表：4 -> 2 -> 1 -> 3

1. Split 1:

• • Slow=1,Pre=2. 断开 2->1.
  • Left:4->2, Right:1->3.

1. Left Recursion (4->2):

• • Slow=2,Pre=4. 断开 4->2.
  • Left:4, Right:2.
  • Merge:2->4.

1. Right Recursion (1->3):

• • Slow=3,Pre=1. 断开 1->3.
  • Left:1, Right:3.
  • Merge:1->3.

1. Final Merge (2->4, 1->3):

• • Compare 2, 1 -> 选 1.
  • Compare 2, 3 -> 选 2.
  • Compare 4, 3 -> 选 3.
  • Compare 4, null -> 选 4.
  • Result:1 -> 2 -> 3 -> 4.