Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
31/05/2017
今天又看了一下這個(gè)題岗照，重溫了一下PriorityQueue。
這題思路：
每次把PriorityQueue里最小的那個(gè)Node擼下來凰浮，然后把這個(gè)最小Node的next結(jié)點(diǎn)加入到PriorityQueue里去。PriorityQueue的意義在于能保證隊(duì)首永遠(yuǎn)是最小的Node捐迫，后面的順序每次add/offer都會(huì)變酵紫，無法保證是按順序的（堆排序我還需要再復(fù)習(xí)一遍）亡鼠，但是我們也不需要后面是按順序的，只需要min heap的堆頂元素就行了稳强。
這題用了堆heap的思想场仲，用的是優(yōu)先權(quán)隊(duì)列實(shí)現(xiàn)的。
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
//none - descending sort
return o1.val - o2.val;
}
});
for (ListNode list : lists) {
if (list != null)
queue.offer(list);
}
ListNode dummy = new ListNode(-1);
ListNode tail = dummy;
while (!queue.isEmpty()) {
tail.next = queue.poll();
tail = tail.next;
//把每個(gè)鏈表上的node全擼下來加入到queue,注意這個(gè)擼下來的過程可能不是連續(xù)的键袱，可能先擼了第一個(gè)鏈表的next就去擼下一個(gè)鏈表了
if (tail.next != null) {
queue.offer(tail.next);
}
}
return dummy.next;
}
一開始我不懂為什么這題的參數(shù)是一個(gè)數(shù)組燎窘，我以為應(yīng)該是好幾個(gè)參數(shù)，每個(gè)參數(shù)是一個(gè)list呢蹄咖。直到看到
if (tail.next != null) {
queue.offer(tail.next);
}
我才恍然大悟褐健，每個(gè)listNode自身就是一個(gè)鏈表呀。
引用CodeGanker的講解：
維護(hù)一個(gè)大小為k的堆澜汤，每次取堆頂?shù)淖钚≡胤诺浇Y(jié)果中蚜迅，然后讀取該元素的下一個(gè)元素放入堆中，重新維護(hù)好俊抵。因?yàn)槊總€(gè)鏈表是有序的谁不，每次又是去當(dāng)前k個(gè)元素中最小的，所以當(dāng)所有鏈表都讀完時(shí)結(jié)束徽诲，這個(gè)時(shí)候所有元素按從小到大放在結(jié)果鏈表中刹帕。
其實(shí)我有點(diǎn)不太懂為什么這k個(gè)list要是已經(jīng)排序好的了吵血，因?yàn)檫@樣看來根本不需要啊（我不懂Java的PriorityQueue是不是每次add/offer一個(gè)元素就會(huì)自動(dòng)排序一次偷溺？如果是的話蹋辅，那無論怎么插入元素，poll出來的永遠(yuǎn)是排好序的queue中的最小元素呀挫掏。侦另。）
對于復(fù)雜度：這個(gè)算法每個(gè)元素要讀取一次，即是k*n次尉共，然后每次讀取元素要把新元素插入堆中要logk的復(fù)雜度褒傅，所以總時(shí)間復(fù)雜度是O(nklogk)“烙眩空間復(fù)雜度是堆的大小殿托，即為O(k)。
