題目
#

leetcode 23 - Merge k Sorted Lists (題目說明請點連結)

題目簡述
#

合併 k 個已排序的鏈表，返回一個新的排序鏈表。

範例
#

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: 合併三個排序鏈表得到一個排序鏈表。

Example 2:

Input: lists = []
Output: []
Explanation: 沒有鏈表需要合併。

解題思路
#

題目要求將 k 個已經排序的鏈表合併成一個排序的鏈表。可以使用 最小堆（Min-Heap 來解決，因為最小堆可以幫助我們在每一步選擇當前最小的元素。

解法
#

使用最小堆將每個鏈表的頭結點加入堆中。
從堆中取出最小的元素，並將該元素的下一個節點加入堆中。
重複步驟2直到堆為空，最終得到合併後的排序鏈表。

例子說明
#

lists = [[1,4,5],[1,3,4],[2,6]]

初始情況：將所有鏈表的頭節點加入堆中，heap = [1,1,2]

第一次取出：
- 取出最小值 1（來自第一個鏈表）
- 將該鏈表的下一個節點 4 加入堆中，heap = [1,2,4]
- 結果鏈表：1
第二次取出：
- 取出最小值 1（來自第二個鏈表）
- 將該鏈表的下一個節點 3 加入堆中，heap = [2,3,4]
- 結果鏈表：1 -> 1
第三次取出：
- 取出最小值 2（來自第三個鏈表）
- 將該鏈表的下一個節點 6 加入堆中，heap = [3,4,6]
- 結果鏈表：1 -> 1 -> 2
第四次取出：
- 取出最小值 3（來自第二個鏈表）
- 將該鏈表的下一個節點 4 加入堆中，heap = [4,4,6]
- 結果鏈表：1 -> 1 -> 2 -> 3
繼續取出…
- 最終結果：1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

完整程式碼
#

java

import java.util.PriorityQueue;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val); // 創建最小堆，按節點值排序

        // 將每個鏈表的頭節點加入堆中
        for (ListNode list : lists) {
            if (list != null) { // 如果鏈表不為空
                heap.offer(list); // 將頭節點加入堆中
            }
        }

        ListNode res = new ListNode(0); // 創建虛擬頭節點
        ListNode cur = res; // 當前指針

        // 合併所有鏈表
        while (!heap.isEmpty()) { // 當堆不為空時繼續處理
            ListNode node = heap.poll(); // 取出堆頂的最小節點
            cur.next = node; // 將節點加入結果鏈表
            cur = cur.next; // 移動當前指針

            // 如果當前節點有下一個節點，則將其加入堆中
            if (node.next != null) {
                heap.offer(node.next); // 將下一個節點加入堆中
            }
        }

        return res.next; // 返回虛擬頭節點的下一個節點
    }
}