【LetMeFly】23.合并 K 個升序鏈表

力扣題目鏈接：https://leetcode.cn/problems/merge-k-sorted-lists/

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

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

?

示例 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

方法一：優先隊列

我們只需要將每個鏈表的 當前節點（初始值是表頭） 放入小根堆中，每次從小根堆中取出一個節點并拼接起來，若這個節點不是表尾節點，則這個節點的下一個節點入隊。

• 時間復雜度$O(N\times \log k)$，其中$n$是所有節點的個數
• 空間復雜度$O(k)$

AC代碼

C++

class Solution {
private:struct cmp {bool operator() (const ListNode* a, const ListNode* b) {return a->val > b->val;}};
public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, cmp> pq;for (ListNode*& node : lists) {if (node) {pq.push(node);}}ListNode* head = new ListNode(), *p = head;while (pq.size()) {ListNode* thisNode = pq.top();pq.pop();p->next = thisNode;p = thisNode;if (thisNode->next) {pq.push(thisNode->next);}}return head->next;}
};

Python

# from typing import List, Optional
# import heapq# # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next# ListNode.__lt__ = lambda a, b: a.val < b.valclass Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:pq = []for node in lists:if node:heapq.heappush(pq, node)head = ListNode()p = headwhile pq:thisNode = heapq.heappop(pq)p.next = thisNodep = thisNodeif thisNode.next:heapq.heappush(pq, thisNode.next)return head.next

同步發文于CSDN，原創不易，轉載請附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/132243952