Problem: 23. 合并 K 個升序鏈表
題目：給你一個鏈表數組，每個鏈表都已經按升序排列。
請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。

整體思路

這段代碼旨在解決一個經典的鏈表問題：合并 K 個排序鏈表 (Merge K Sorted Lists)。問題要求將一個包含 K 個已排序鏈表的數組，合并成一個單一的、大的有序鏈表。

該實現采用了一種簡單直接的 逐一合并 (One by One Merging) 的策略。它將“合并K個鏈表”的問題，簡化為了“重復執行 K-1 次‘合并兩個鏈表’”的問題。

其核心邏輯步驟如下：

1. 處理邊界情況：

   • 首先，檢查輸入的鏈表數組 lists 是否為 null 或空。如果是，直接返回 null。
   • 如果數組中只有一個鏈表，直接返回該鏈表。

2. 迭代合并：

   • 算法將 lists[0] 作為“累加器”或“基準鏈表”。
   • 通過一個 for 循環，從 i=1 開始，依次將 lists[i] 合并到 lists[0] 中。
   • lists[0] = merge(lists[0], lists[i]); 這一行是核心。它調用一個輔助函數 merge，將當前的合并結果 lists[0] 與下一個鏈表 lists[i] 進行合并，然后用新的、更長的合并結果來更新 lists[0]。
   • 這個過程會重復 K-1 次。

3. merge 輔助函數：

   • 這個私有函數 merge(l1, l2) 是一個標準的“合并兩個有序鏈表”的實現。
   • 它使用哨兵節點 dummy 和一個 cur 指針，通過迭代比較 l1 和 l2 的節點值，將較小的節點鏈接到結果鏈表的末尾，直到其中一個鏈表被遍歷完。
   • 最后，將另一個鏈表中剩余的部分直接追加到結果鏈表的末尾。
   • 這個函數在每次主循環中被調用。

4. 返回結果：

   • 當 for 循環結束后，lists[0] 中就存儲了所有 K 個鏈表合并后的最終結果，將其返回。

雖然這個方法邏輯清晰，易于理解，但它并不是最高效的解決方案，因為在合并過程中存在大量的重復比較。

完整代碼

/*** Definition for singly-linked list.*/
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 {/*** 合并 K 個排序鏈表。* @param lists 一個包含 K 個排序鏈表的數組* @return 合并后的單一排序鏈表*/public ListNode mergeKLists(ListNode[] lists) {// 處理邊界情況：輸入為空或沒有鏈表if (null == lists || lists.length == 0) {return null;}int n = lists.length;// 如果只有一個鏈表，直接返回它if (1 == n) {return lists[0];}// 步驟 1: 逐一合并// 將 lists[0] 作為基礎，依次將 lists[1], lists[2], ... 合并進來for (int i = 1; i < n; i++) {// 調用輔助函數合并當前的累積結果 lists[0] 和下一個鏈表 lists[i]lists[0] = merge(lists[0], lists[i]);}// 循環結束后，lists[0] 就是最終的合并結果return lists[0];}/*** 輔助函數：合并兩個有序鏈表。* @param l1 第一個有序鏈表* @param l2 第二個有序鏈表* @return 合并后的有序鏈表*/private ListNode merge(ListNode l1, ListNode l2) {// 使用哨兵節點簡化合并邏輯ListNode dummy = new ListNode();ListNode cur = dummy;// 比較兩個鏈表的節點，將較小的鏈接到結果鏈表while (null != l1 && null != l2) {if (l1.val < l2.val) {cur.next = l1;l1 = l1.next;} else {cur.next = l2;l2 = l2.next;}cur = cur.next;}// 將剩余的鏈表部分直接追加到末尾cur.next = null == l1 ? l2 : l1;return dummy.next;}
}

時空復雜度

時間復雜度：O(K * N)

1. merge 函數的復雜度：合并兩個長度分別為 m 和 n 的鏈表，時間復雜度是 O(m + n)。
2. 主循環分析：
   • 設 K 是鏈表的數量，N 是所有鏈表的節點總數。為簡化分析，我們假設每個鏈表平均有 N/K 個節點。
   • 第一次合并 (i=1): merge(lists[0], lists[1])。lists[0] 長度為 N/K，lists[1] 長度為 N/K。耗時 O(2N/K)。合并后 lists[0] 長度變為 2N/K。
   • 第二次合并 (i=2): merge(lists[0], lists[2])。lists[0] 長度為 2N/K，lists[2] 長度為 N/K。耗時 O(3N/K)。合并后 lists[0] 長度變為 3N/K。
   • …
   • 第 i 次合并: lists[0] 長度為 i * (N/K)，lists[i] 長度為 N/K。耗時 O((i+1)N/K)。
   • 總時間 ≈ Σ(i=1 to K-1) (i+1)N/K = (N/K) * Σ(j=2 to K) j = (N/K) * (K(K+1)/2 - 1)。
   • 這個表達式的最高階項是 (N/K) * (K^2 / 2)，所以復雜度是 O(N * K)。

綜合分析：
該算法的時間復雜度為 O(N * K)，其中 N 是總節點數，K 是鏈表數。當 K 較大時，這個效率并不理想。

空間復雜度：O(1)

1. 主要存儲開銷：
   • merge 函數內部使用了 dummy 和 cur 等常數個指針變量。
   • 主函數 mergeKLists 也沒有使用與 N 或 K 成比例的額外數據結構。它是在原地修改 lists 數組的第一個元素。

綜合分析：
算法所需的額外輔助空間是常數級別的。因此，其空間復雜度為 O(1)。這是該解法的一個優點。