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 = [[]]
輸出：[]
提示：
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
解題思路：
本題有多種解題思路，
如順序合并，即最樸素的方法：用一個變數 ans 來維護以及合并的鏈表，第 ii 次回圈把第 ii 個鏈表和 ans 合并，答案保存到 ans 中，使用到了兩兩歸并的程序，但是時間復雜度會達到O(k2n)
還有一種是使用分治演算法，但程序較為復雜
本文僅介紹一種時間復雜度較優，且實作非常容易的演算法，即借助Java的優先級佇列，Java優先級佇列的具體介紹請參看：Java優先級佇列PriorityQueue將K個鏈表中的所有結點全部入隊，然后每次從佇列中取出隊頭元素，即佇列中的最小元素使用尾插法插入到虛擬頭結點的后面，最終就可以將原K個鏈表按照從小到大的順序排序，時間復雜度O(nlogn),但空間復雜度也為O(n)
實作代碼：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
//創建優先級佇列，傳入一個比較器，比較器和優先級佇列的引數都是ListNode
Queue<ListNode> pqueue=new PriorityQueue<ListNode>(new Comparator<ListNode>(){
@Override
//實作Comparator介面的compare方法，兩個listNode排序時按照val值
public int compare(ListNode o1, ListNode o2) {
return o1.val-o2.val;
}
});
//遍歷K個升序鏈表，將其全部加入到優先級佇列中
for(ListNode li:lists){
ListNode p=li;
while(p!=null){
pqueue.offer(p);
p=p.next;
}
}
ListNode head=new ListNode(-1); //創建虛擬頭結點
//我們使用的尾插法，尾插法能夠保證元素按照插順序進行組織，所以要維護一個尾結點
ListNode r=head;
//每次將優先級佇列中的隊頭元素取出，加入到鏈表中
while(!pqueue.isEmpty()){
ListNode p=pqueue.poll();
r.next=p;
r=r.next;
}
//最終一定要將r.next置為空，否則可能會發生錯誤
r.next=null;
return head.next; //回傳虛擬頭結點的next指標，
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/260566.html
標籤：java
上一篇：迷宮問題（簡單模擬）