解題思路：
- 找到鏈表中點： 使用快慢指針法，快指針每次移動兩步，慢指針每次移動一步。當快指針到達末尾時，慢指針指向中點。
- 遞歸分割與排序： 將鏈表從中點處分割為左右兩個子鏈表，分別對這兩個子鏈表遞歸排序。
- 合并有序子鏈表： 將兩個已排序的子鏈表合并成一個有序鏈表。
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)?。（遞歸棧深度）
解題思路：
- 初始化優先隊列： 將所有鏈表的頭節點加入堆中，堆頂元素為當前最小值。
- 構建結果鏈表： 每次從堆頂取出最小節點，添加到結果鏈表中，并將其下一個節點加入堆中（若存在）。
- 處理空鏈表： 跳過輸入數組中的空鏈表，避免無效操作。
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)，用于存儲堆中的節點。
)
