目錄

23. 合并 K 個升序鏈表

題目描述：

實現代碼與解析：

優先級隊列：

原理思路：

---

23. 合并 K 個升序鏈表

題目描述：

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

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

示例 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 = [[]]
輸出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i]?按?升序?排列
• lists[i].length?的總和不超過?10^4

實現代碼與解析：

優先級隊列：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:struct Node{int val;ListNode* ptr;bool operator < (const Node &node) const{return val > node.val; //小頂堆}};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<Node> q; // 優先級隊列for (int i = 0; i < lists.size(); i++){if (lists[i]) q.push({lists[i]->val, lists[i]}); // 入隊}ListNode* head = new ListNode(); // 頭節點ListNode* cur = head;while(q.size()){auto t = q.top(); q.pop(); // 出隊cur->next = t.ptr;cur = cur->next;auto nt = t.ptr->next; if (nt) q.push({nt->val, nt}); // 已經出隊的節點將其下一個節點入隊}return head->next;}
};

原理思路：

? ? ? ? 優先級隊列，小頂堆，定義一個結構體，里面存有節點值用于堆的比較，指針，用于記錄鏈表中節點的位置，每次取出節點，記得把其后面相連的節點入隊比較，直到為空為止。很簡單，不再詳細解釋了。