LeetCode 解题思路 17（Hot 100）

解题思路：

1. 找到链表中点： 使用快慢指针法，快指针每次移动两步，慢指针每次移动一步。当快指针到达末尾时，慢指针指向中点。
2. 递归分割与排序： 将链表从中点处分割为左右两个子链表，分别对这两个子链表递归排序。
3. 合并有序子链表： 将两个已排序的子链表合并成一个有序链表。

Java代码：

class Solution {public ListNode sortList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode slow = head, fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}ListNode mid = slow.next; slow.next = null;ListNode left = sortList(head);ListNode right = sortList(mid);return merge(left, right);}private ListNode merge(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(-1);ListNode current = dummy;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {current.next = l1;l1 = l1.next;} else {current.next = l2;l2 = l2.next;}current = current.next;}current.next = (l1 != null) ? l1 : l2;return dummy.next;}
}

复杂度分析：

• 时间复杂度： 归并排序的时间复杂度为 ​O(nlogn)。
• 空间复杂度： O(log n)​。（递归栈深度）

解题思路：

1. 初始化优先队列： 将所有链表的头节点加入堆中，堆顶元素为当前最小值。
2. 构建结果链表： 每次从堆顶取出最小节点，添加到结果链表中，并将其下一个节点加入堆中（若存在）。
3. 处理空链表： 跳过输入数组中的空链表，避免无效操作。

Java代码：

class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0) return null;PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);for (ListNode node : lists) {if (node != null) {minHeap.offer(node);}}ListNode dummy = new ListNode(-1);ListNode current = dummy;while (!minHeap.isEmpty()) {ListNode smallest = minHeap.poll();current.next = smallest;current = current.next;if (smallest.next != null) {minHeap.offer(smallest.next);}}return dummy.next;}
}

复杂度分析：

• 时间复杂度： O(nklogk)，其中 n 是总节点数，k 是链表数量。
• 空间复杂度： O(k)，用于存储堆中的节点。