目錄

1:題目描述：

2.算法思想：

3.代碼展示：

1:題目描述：

給你一個鏈表數組，每個鏈表都已經按升序排列。

請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。

示例 1：

輸入：lists = [[1,4,5],[1,3,4],[2,6]]
輸出：[1,1,2,3,4,4,5,6]
解釋：鏈表數組如下：
[1->4->5,1->3->4,2->6
]
將它們合并到一個有序鏈表中得到。
1->1->2->3->4->4->5->6

示例 2：

輸入：lists = []
輸出：[]

示例 3：

輸入：lists = [[]]
輸出：[]

2.算法思想：

1. 義比較器??：

   • 由于priority_queue默認是大根堆（堆頂元素最大），而我們希望每次取出最小的元素
   • 自定義比較器Compare，當l1->val > l2->val時返回true，這樣構造出小根堆

2. ??初始化優先級隊列??：

   • 創建一個存儲ListNode*的小根堆pq

3. ??將所有鏈表元素入隊??：

   • 遍歷輸入的lists數組
   • 對于每個鏈表，從頭節點開始，將所有節點依次加入優先級隊列
   • 注意：這里直接將原鏈表的節點拆散加入隊列，會破壞原鏈表結構

4. ??構建結果鏈表??：

   • 創建一個虛擬頭節點dummy簡化操作
   • 使用指針p跟蹤當前鏈表的末尾
   • 循環從優先級隊列中取出最小元素（堆頂）：
     • 將取出的節點連接到p->next
     • p移動到新連接的節點
     • 從隊列中移除該節點

5. ??返回結果??：

   • 返回dummy.next，即合并后的鏈表頭節點

3.代碼展示：

 //因為priority_queue默認是大根堆，堆頂是最大的元素，所以我們需要自定比較器，讓它從小到大class Compare {public:bool operator()(ListNode* l1, ListNode* l2) {return l1->val > l2->val;}
};ListNode* mergeKLists(vector<ListNode*>& lists) {//使用優先級隊列，priority_queue<ListNode*, vector<ListNode*>, Compare>pq;//把lists的每個元素都入隊for (int i = 0; i < lists.size(); i++) {while (lists[i]){pq.push(lists[i]);lists[i] = lists[i]->next;}}//重新定義一個鏈表ListNode dummy(-1);ListNode* p = &dummy;//始終指向最后一個元素,開始鏈表為空，故指向頭節點//接下來開始循環pq，while (!pq.empty()){p->next = pq.top();pq.pop();p = p -> next;}return dummy.next;}

23. 合并 K 個升序鏈表 - 力扣（LeetCode）https://leetcode.cn/problems/merge-k-sorted-lists/