給定一個鏈表數(shù)組，每個鏈表都已經(jīng)按升序排列。
請將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。
輸入：lists = [[1,4,5],[1,3,4],[2,6]] 輸出：[1,1,2,3,4,4,5,6] 解釋：鏈表數(shù)組如下： [ 1->4->5, 1->3->4, 2->6 ] 將它們合并到一個有序鏈表中得到。 1->1->2->3->4->4->5->6
? ? ? ?這道題看似困難題，其實還是比較容易好想的，我們可以維護一個優(yōu)先最小隊列，然后聲明一個虛擬頭結(jié)點，每次出一個最小的節(jié)點掛載在已經(jīng)掛載節(jié)點的后面，當隊列為空時，就說明我們K個升序列表已經(jīng)合并完成
文章來源：http://www.zghlxwxcb.cn/news/detail-650324.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-650324.html
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null||lists.length==0){
return null;
}
//自定義比較器
PriorityQueue<ListNode> queue=new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val-o2.val;
}
});
//將K個節(jié)點的頭結(jié)點入隊
for(ListNode node:lists){
if(node!=null){
queue.offer(node);
}
}
//創(chuàng)建一個虛擬頭結(jié)點
ListNode dummyNode=new ListNode(-1);
ListNode curNode=dummyNode;
while(!queue.isEmpty()){
ListNode cur=queue.poll();
curNode.next=cur;
//更新curNode
curNode=curNode.next;
//如果當前節(jié)點的next不為空，則讓下一個節(jié)點進行入隊
if(cur.next!=null){
queue.offer(cur.next);
}
}
return dummyNode.next;
}到了這里，關于面試熱題（合并K個升序鏈表）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
