二十四 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)时间复杂度和常数级空间复杂度下对链表进行排序吗关键代码解析代码作用为什么for (int step 1; step length; step * 2)控制子链表长度1→2→4→8直到覆盖整个链表cut(left, step)切出长度为 step 的段物理切断链表返回下一段头head.next null切断链表让左/右段独立成链表merge(left, right)合并两段有序链表21题的标准技巧prev指针连接各段合并结果保持链表连续性while (prev.next ! null)移动 prev 到末尾为下一次合并做准备执行流程图解以[4, 2, 1, 3]为例length4原始: 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 个节点返回第 n1 个节点 * 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; } }