這道題的題目是合并k個有序的鏈表，標定難度為Hard，詳細需求：

合并k個有序的鏈表，返回一個新的有序鏈表。

例子:

Input:

1->4->5,

1->3->4,

2->6

Output: 1->1->2->3->4->4->5->6

邏輯不復雜，合并k個有序鏈表，我想不出來怎么一次性合并k個鏈表，貌似也不是不可以，但是代碼感覺有點亂。但是更簡單的方法就是反正我們剛做過21題，所以我們知道怎么合并兩個有序鏈表。我們就一次合并兩個有序鏈表，最后合并完全部的鏈表。這道題我們提供暴力解法、分而治之以及最小堆三種解法。

暴力解法

思路很簡單一個for循環一個一個鏈表的去合并。總共需要合并k-1次。代碼里面直接調用了21題的mergeTwoLists方法：

分而治之解法

分而治之怎么解這道題呢？其實大概一想就知道了，就是把問題分成兩半，然后把子問題再分成兩半，直到問題小到只剩兩個鏈表，然后再返回一步一步合并結果。分析完了你會發現這個問題跟歸并排序(Merge-Sort)的思路是一樣的。所以，我們的解法就完全模仿了《算法導論》的歸并排序的寫法。那么復雜度也就是nlog(n).

最小堆解法

我們今天討論了堆和堆排序算法。于是我給23題加入了一個用最小堆解決的方案。這里用的堆算法和《Leetcode專題 堆結構和堆排序》中提供的最大堆算法邏輯完全一樣，只是最大換成最小而已。最大堆原理可以參看此文。

這段代碼的思路是，首先把全部列表輸入到數組里面，然后用數組構建一個最小堆，然后循環輸出最小元素，串成一個鏈表輸出。

你可以在Github代碼里面看到包括最小堆實現的全部代碼，這里只提供調用了我寫的最小堆的代碼的截圖：

這道題是分而治之，如果你對分而治之算法本身不太熟悉，請參閱《算法導論》。《算法導論》一書在2.3.1章節介紹了Merge Sort(歸并排序)，在第4章“分而治之”介紹了4.1 the maximum-subarray problem(最大子數組問題)，4.2 Strassen’s algorithm for matrix multiplication (Strassen的矩陣乘法算法)。

也請參閱我的文章《LeetCode專題 分而治之》，文章中實現了算法導論里面的這三個分而治之的問題的代碼，以及LeetCode相關問題的一個列表。

也請參閱《Leetcode專題 堆結構和堆排序》，文章介紹了堆和堆排序，以及最大堆的實現。本題我們實現了一個最小堆，跟最大堆原理一樣，只需要做幾行修改即可。

打賞

微信掃一掃，打賞作者吧～

總結

以上是生活随笔為你收集整理的merge k sorted lists java_LeetCode 第23题 Merge k Sorted Lists【分而治之】【最小堆】（Java）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。