二十四 148. 排序链表

148. 排序链表https://leetcode.cn/problems/sort-list/

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

关键代码解析

执行流程图解

以[4, 2, 1, 3]为例（length=4）：

原始: 4 → 2 → 1 → 3 ========== step = 1: 每1个合并成2个有序 ========== 初始: dummy → 4 → 2 → 1 → 3 ↑ curr 第1次合并： left = [4], cut后 leftEnd = 2 right = [2], cut后 rightEnd = 1 merge([4], [2]) = [2, 4] dummy → 2 → 4 1 → 3 ↑ ↑ prev curr 第2次合并： left = [1], right = [3] merge([1], [3]) = [1, 3] dummy → 2 → 4 → 1 → 3 ↑ prev 结果: 2 → 4 → 1 → 3（两个长度为2的有序段） ========== step = 2: 每2个合并成4个有序 ========== dummy → 2 → 4 → 1 → 3 ↑ curr 第1次合并： left = [2, 4], cut 2步后 leftEnd = 1 right = [1, 3], cut 2步后 rightEnd = null merge([2,4], [1,3]) = [1, 2, 3, 4] dummy → 1 → 2 → 3 → 4 ↑ prev curr = null，结束 ========== step = 4: 4 < 4? 否，结束 ========== 返回 [1, 2, 3, 4] ✅

/** * Definition for singly-linked list. * public 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 { public ListNode sortList(ListNode head) { if(head == null || head.next == null){ return head;// 空或单节点，已有序 } // ========== 步骤1: 计算链表长度 ========== int length = 0; ListNode node = head; while(node != null){ length++; node = node.next; } // ========== 步骤2: 自底向上归并排序 ========== ListNode dummy = new ListNode(0); dummy.next = head; // step: 当前要合并的子链表长度（1, 2, 4, 8...） for(int step = 1; step < length; step *= 2){ ListNode prev = dummy;// 上一段有序链表的尾 ListNode curr = dummy.next;// 当前待处理位置 while(curr != null){ // 切出左半部分 [curr, leftEnd)，长度为 step ListNode left = curr; ListNode leftEnd = cut(left, step); // 切出右半部分 [leftEnd, rightEnd)，长度为 step ListNode right = leftEnd; ListNode rightEnd = cut(right, step); // 记录下一轮的起点 curr = rightEnd; // 合并左右两部分，接到 prev 后面 prev.next = merge(left, right); // prev 移动到合并后链表的末尾 while(prev.next != null){ prev = prev.next; } } } return dummy.next; } /** * 切断链表：从 head 开始保留 n 个节点，返回第 n+1 个节点 * head -> n1 -> n2 -> ... -> nn -> next * 变成: head -> n1 -> ... -> nn -> null * 返回: next */ private ListNode cut(ListNode head, int n){ if(head == null){ return null; } // 走 n-1 步，到达第 n 个节点 for(int i = 1; i < n && head.next != null; i++){ head = head.next; } ListNode next = head.next;// 保存断点 head.next = null;// 切断 return next; // 返回下一段的头 } /** * 合并两个有序链表（21题的标准写法） */ private ListNode merge(ListNode l1, ListNode l2){ ListNode dummy = new ListNode(0); ListNode cur = dummy; 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 dummy.next; } }