【LeetCode 热题 100】148. 排序链表——（解法二）分治
Problem: 148. 排序链表
题目：给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
【LeetCode 热题 100】148. 排序链表——（解法一）暴力解
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(N log N)
- 空间复杂度：O(log N)
整体思路
这段代码旨在解决 “排序链表” 的问题，并且采用了符合题目进阶要求（O(N log N) 时间复杂度和 O(1) 空间复杂度）的 自顶向下归并排序 (Top-down Merge Sort) 算法。归并排序是一种经典的分治 (Divide and Conquer) 算法，非常适合链表这种数据结构。
算法的核心思路可以分解为三个主要部分：分割（找到中点）、递归排序（解决子问题） 和 合并（合并有序子链表）。
-
分割 (Find Midpoint)：
- 快慢指针法：为了将链表平均地分成两半，算法使用了经典的“快慢指针”技巧。
slow指针每次移动一步，fast指针每次移动两步。 - 当
fast指针到达链表末尾时，slow指针恰好位于链表的中点或中点前一个位置。 - 一个额外的
pre指针被用来记录slow的前一个节点。 - 断开链表：找到中点后，通过
pre.next = null;将链表从中间断开，形成两个独立的子链表。head指向第一半的头，slow指向第二半的头。
- 快慢指针法：为了将链表平均地分成两半，算法使用了经典的“快慢指针”技巧。
-
递归排序 (Recursive Sort)：
- 递归基 (Base Case)：
if (null == head || null == head.next)。如果链表为空或只有一个节点，那么它自然是有序的，直接返回head。这是递归的出口。 - 分治：对于被分割开的两个子链表，分别递归地调用
sortList函数，即sortList(head)和sortList(slow)。这个过程会不断地将链表分割下去，直到每个子链表都只剩一个节点（满足递归基），然后再开始合并。
- 递归基 (Base Case)：
-
合并 (Merge)：
- 辅助函数
merge：这个函数接收两个已经排好序的子链表head1和head2，并将它们合并成一个单一的、有序的链表。 - 合并逻辑：
- 使用一个
dummy哨兵节点和cur指针来构建新的合并链表。 - 通过一个
while循环，比较head1和head2当前节点的值。将值较小的那个节点链接到cur.next，并移动相应链表的指针。 - 循环结束后，可能有一个链表还有剩余的节点（因为另一个已经遍历完）。这些剩余节点已经是有序的，并且都比已合并部分大，所以直接将它们全部链接到结果链表的末尾即可 (
cur.next = null == head1 ? head2 : head1;)。
- 使用一个
sortList函数的最后一步就是返回这个merge函数的结果。
- 辅助函数
完整代码
/*** Definition for singly-linked list.*/
class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}class Solution {/*** 对一个单向链表进行升序排序（自顶向下归并排序）。* @param head 链表的头节点* @return 排序后链表的头节点*/public ListNode sortList(ListNode head) {// 递归终止条件：链表为空或只有一个节点，已是有序。if (null == head || null == head.next) {return head;}// 步骤 1: 使用快慢指针法找到链表中点并分割链表。ListNode pre = head; // pre 记录 slow 的前一个节点，用于断开链表。ListNode slow = head; // 慢指针，每次走一步。ListNode fast = head; // 快指针，每次走两步。while (null != fast && null != fast.next) {pre = slow;slow = slow.next;fast = fast.next.next;}// 当 fast 到达末尾时，slow 在中点。断开链表。pre.next = null;// 步骤 2: 递归地对两个子链表进行排序。ListNode head1 = sortList(head); // 第一半ListNode head2 = sortList(slow); // 第二半// 步骤 3: 合并两个已排序的子链表。return merge(head1, head2);}/*** 辅助函数：合并两个有序链表。* @param head1 第一个有序链表* @param head2 第二个有序链表* @return 合并后的有序链表*/private ListNode merge(ListNode head1, ListNode head2) {// 使用哨兵节点简化合并逻辑。ListNode dummy = new ListNode();ListNode cur = dummy;// 比较两个链表的头节点，将较小的链接到结果链表。while (null != head1 && null != head2) {if (head1.val < head2.val) {cur.next = head1;head1 = head1.next;} else {cur.next = head2;head2 = head2.next;}cur = cur.next;}// 将剩余的链表部分直接链接到末尾。cur.next = null == head1 ? head2 : head1;return dummy.next;}
}
时空复杂度
时间复杂度：O(N log N)
- 分割链表：每次调用
sortList时，找到中点的快慢指针法需要遍历当前子链表一次。设当前子链表长度为n，则耗时 O(n)。 - 递归深度：归并排序的分割过程会将链表不断对半切分，这个过程的深度是
log N。 - 每层合并：在递归的每一层，
merge操作需要遍历该层的所有节点一次。无论链表被分得多散，每一层的节点总数都是N。所以每层的合并总耗时是 O(N)。
综合分析：
总的时间复杂度 = 递归层数 * 每层的时间复杂度 = O(log N) * O(N) = O(N log N)。
空间复杂度：O(log N)
- 主要存储开销：该算法是“原地”的，因为它没有创建与输入规模成比例的额外数据结构（如数组）来存储节点。
merge函数中的dummy和cur都是常数空间。 - 递归栈空间：由于使用了递归，函数调用会占用调用栈的空间。递归的深度是
log N。因此，递归栈所需的空间复杂度是 O(log N)。
综合分析：
算法所需的额外空间主要由递归调用栈的深度决定。因此，其空间复杂度为 O(log N)。这基本满足了题目对空间复杂度的进阶要求（严格的 O(1) 需要自底向上的归并排序，但 O(log N) 通常也被接受）。
参考灵神