好久沒更新了篮昧，今天我又來了。一直看我文章的朋友可能會發(fā)現(xiàn)民傻，我之前多次提到堆這個數(shù)據(jù)結(jié)構(gòu)胰默，它可以幫助我們快速地在一堆數(shù)據(jù)中场斑，找到符合某個條件的最大或者最小的元素。今天我們還是要來談?wù)撍Ｊ穑瑳]辦法漏隐，它就是這么強(qiáng)大又好用。
來看這樣一道題目：給定K個排序好的鏈表奴迅，排序好合并到一個列表中去青责。
示例 1:
輸入: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4]
輸出: [1, 2, 3, 3, 4, 6, 6, 7, 8]
示例 2:
輸入: L1=[5, 8, 9], L2=[1, 7]
輸出: [1, 5, 7, 8, 9]
拿到這道題的第一感覺似乎也不是很難嘛，我們可以把所有元素加到一個列表里面去然后再排序取具，時間復(fù)雜度也不過是O(N?logN)脖隶。這里N是K個鏈表所有元素之和。
不過這么做的話暇检，其實(shí)鏈表們排沒排序都一樣产阱，既然題目告訴我們鏈表是排序好的，那它肯定是更優(yōu)解法的重要條件块仆。我們得想辦法利用好這個條件构蹬。我們想要讓最終的列表排好序，那肯定要把所有元素里最小的元素放在前面悔据。既然給我們的K個鏈表都是排好序的庄敛，那我們只要比較它們的第一個元素就能得到最終列表的最小元素里。拿到最小元素我們就添加到最終列表里科汗，按照這個思路藻烤，我們在每一步都可以拿到K個鏈表中的最小元素，最后得到我們想要的結(jié)果头滔。
那說到在K個元素中找最小的元素怖亭，我們又想到堆了。那我們再來盤一下用堆我們該怎么做：
- 把每個鏈表第一個元素插入到最小堆
- 從堆中取出最小的元素添加到結(jié)果列表中
- 再從拿出去的元素所在的那個鏈表中取出下一個元素放到堆中
- 重復(fù)第2步跟第3步坤检，我們可以保證所有元素添加到了結(jié)果列表中且有序
就拿第一個例子來說依许，我們再來詳細(xì)討論一下這個過程。
給定的鏈表: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4]
-
在從每個鏈表中取出第一個元素時缀蹄，我們的堆是這樣的：
-
我們會取出位于堆頂?shù)脑厍吞尤氲胶喜⒌牧斜碇校缓蟀堰@個元素所在鏈表中的的下一個元素加入到堆中：
-
那么缺前，我們再次把堆頂?shù)脑厝〕龇诺浇Y(jié)果列表中蛀醉，把下一個元素添加到堆中：
-
重復(fù)上面的步驟，取出堆頂元素加入到結(jié)果列表中衅码，再把它的下一個元素加入到堆中拯刁。這里有兩個3，可以隨便選逝段，但是要注意選了哪個就把哪個的下一個元素加到堆中垛玻，這個次序很重要割捅。
最終我們就能得到一個排序好的列表啦！
public static ListNode merge(ListNode[] lists) {
PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>((n1, n2) -> n1.value - n2.value);
// 把第一個元素添加到堆
for (ListNode root : lists)
if (root != null)
minHeap.add(root);
// 從最小堆中取出最小的元素并加入到結(jié)果中
// 如果它在鏈表中還有下一個元素帚桩，那么把它的這個下一個元素添加到堆中
ListNode resultHead = null, resultTail = null;
while (!minHeap.isEmpty()) {
ListNode node = minHeap.poll();
if (resultHead == null) {
resultHead = resultTail = node;
} else {
resultTail.next = node;
resultTail = resultTail.next;
}
if (node.next != null)
minHeap.add(node.next);
}
return resultHead;
}
看看亿驾，這個問題有了堆這個數(shù)據(jù)結(jié)構(gòu)變得格外簡單，復(fù)雜度也得到了優(yōu)化账嚎！這里時間復(fù)雜度在O(N?logK)莫瞬，而空間復(fù)雜度在O(K)。這就是我們常聽到的多路歸并算法的核心思想郭蕉，以后再看到類似題目知道該怎么辦了吧疼邀？
最后的最后，我再強(qiáng)調(diào)下復(fù)習(xí)一下常見的數(shù)據(jù)結(jié)構(gòu)的重要性召锈，會對我們解題大有幫助旁振。就拿這道題來說，思路其實(shí)很簡單涨岁，但是如果不知道或者忘了堆的用法规求，這道題大概率只能想到把所有元素加入結(jié)果列表再排序，豈不可惜卵惦？
