千问 LeetCode 148. 排序链表 Java实现

题目分析核心思路归并排序。链表天然适合归并排序不需要额外空间。步骤分割快慢指针找到中点断开链表。递归排序左右两半分别排序。合并合并两个有序链表。时间复杂度O(n log n)空间复杂度O(log n)递归栈。Java 实现class Solution {public ListNode sortList(ListNode head) {if (head null || head.next null) {return head;}// 1. 快慢指针找中点slow 最终指向前半段的最后一个节点 ListNode slow head, fast head.next; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } // 2. 断开链表分成两半 ListNode mid slow.next; slow.next null; // 3. 递归排序左右两半 ListNode left sortList(head); ListNode right sortList(mid); // 4. 合并两个有序链表 return merge(left, right); } 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; }}关键点说明要点 说明快慢指针 fast head.next 而非 head确保偶数长度时 slow 停在前半段末尾避免死循环断开链表 slow.next null 是关键否则递归不会终止合并操作 经典的双指针合并时间复杂度 O(n)递归终止 head null head.next null 时直接返回进阶自底向上归并排序O(1) 空间如果要求空间复杂度 O(1)可以用迭代版归并排序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. 自底向上归并步长从 1 开始每次翻倍 ListNode dummy new ListNode(0, head); for (int step 1; step length; step 1) { ListNode prev dummy; ListNode curr dummy.next; while (curr ! null) { // 拆分左半部分 ListNode left curr; ListNode right split(left, step); // 拆分右半部分并返回下一段的起始节点 curr split(right, step); // 合并左右两部分prev 指向合并后的尾节点 prev merge(left, right, prev); } } return dummy.next; } // 从 head 开始切出 n 个节点返回第 n1 个节点即下一段头部 private ListNode split(ListNode head, int n) { if (head null) return null; for (int i 1; i n head.next ! null; i) { head head.next; } ListNode next head.next; head.next null; return next; } // 合并 l1 和 l2接到 prev 后面返回合并后的尾节点 private ListNode merge(ListNode l1, ListNode l2, ListNode prev) { ListNode curr prev; while (l1 ! null l2 ! null) { if (l1.val l2.val) { curr.next l1; l1 l1.next; } else { curr.next l2; l2 l2.next; } curr curr.next; } curr.next (l1 ! null) ? l1 : l2; // 找到合并后的尾节点 while (curr.next ! null) { curr curr.next; } return curr; }}⚠️ 面试中如果面试官问能不能做到 O(1) 空间就写迭代版。一般情况下递归版已经足够。需要我把 Python3 或 Rust 版本也写出来吗