LeetCode 上最難的鏈表算法題，沒有之一！

題目來源於 LeetCode 第 23 號問題：合併 K 個排序鏈表。

該題在 LeetCode 官網上有關於鏈表的問題中標註為最難的一道題目：難度為 Hard ，通過率在鏈表 Hard 級別目前最低。

題目描述

合併 k 個排序鏈表，返回合併後的排序鏈表。請分析和描述算法的複雜度。

示例:

輸入:
[
 1->4->5,
 1->3->4,
 2->6
]
輸出: 1->1->2->3->4->4->5->6

輸入

圖一

輸出

圖二

題目分析一

這裡需要將這 k 個排序鏈表整合成一個排序鏈表，也就是說有多個輸入，一個輸出，類似於漏斗一樣的概念。

因此，可以利用最小堆的概念。如果你對堆的概念不熟悉，

可以戳這先了解一下~

取每個 Linked List 的最小節點放入一個 heap 中，排序成最小堆。然後取出堆頂最小的元素，放入輸出的合併 List 中，然後將該節點在其對應的 List 中的下一個節點插入到 heap 中，循環上面步驟，以此類推直到全部節點都經過 heap。

由於 heap 的大小為始終為 k ，而每次插入的複雜度是 logk ，一共插入了 nk 個節點。時間複雜度為 O(nklogk)，空間複雜度為O(k)。

代碼實現

class Solution {
 public ListNode mergeKLists(ListNode[] lists) {
 //用heap(堆)這種數據結構，也就是 java 裡面的 PriorityQueue
 PriorityQueue<listnode> pq = new PriorityQueue<>(new Comparator<listnode>() {
 public int compare(ListNode a, ListNode b) {
 return a.val-b.val;
 }
 });
 ListNode ret = null, cur = null;
 for(ListNode node: lists) {
 if(null != node) {
 pq.add(node); 
 }
 }
 while(!pq.isEmpty()) {
 ListNode node = pq.poll();
 if(null == ret) {
 ret = cur = node;
 }
 else {
 cur = cur.next = node; 

 }
 if(null != node.next) {
 pq.add(node.next); 
 }
 }
 return ret;
 }
}
/<listnode>/<listnode>

題目分析二

這道題需要合併 k 個有序鏈表，並且最終合併出來的結果也必須是有序的。如果一開始沒有頭緒的話，可以先從簡單的開始：合併 兩 個有序鏈表。

合併兩個有序鏈表：將兩個有序鏈表合併為一個新的有序鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例：

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

這道題目按照題目描述做下去就行：新建一個鏈表，比較原始兩個鏈表中的元素值，把較小的那個鏈到新鏈表中即可。需要注意的一點時由於兩個輸入鏈表的長度可能不同，所以最終會有一個鏈表先完成插入所有元素，則直接另一個未完成的鏈表直接鏈入新鏈表的末尾。

所以代碼實現很容易寫：

class Solution {
 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 //新建鏈表
 ListNode dummyHead = new ListNode(0);
 ListNode cur = dummyHead;
 while (l1 != null && l2 != null) {
 if (l1.val < l2.val) {
 cur.next = l1;
 cur = cur.next;
 l1 = l1.next;
 } else {
 cur.next = l2;
 cur = cur.next;
 l2 = l2.next;
 }
 }
 // 注意點：當有鏈表為空時，直接連接另一條鏈表
 if (l1 == null) {
 cur.next = l2;
 } else {
 cur.next = l1;
 }
 return dummyHead.next;
 }

現在回到一開始的題目：合併 K 個排序鏈表。

合併 K 個排序鏈表 與 合併兩個有序鏈表 的區別點在於操作有序鏈表的數量上，因此完全可以按照上面的代碼思路來實現合併 K 個排序鏈表。

這裡可以參考

歸併-分治

代碼實現

根據上面的動畫，實現代碼非常簡單也容易理解，先劃分，直到不能劃分下去，然後開始合併。

class Solution {
 public ListNode mergeKLists(ListNode[] lists){
 if(lists.length == 0)
 return null;
 if(lists.length == 1)
 return lists[0];
 if(lists.length == 2){
 return mergeTwoLists(lists[0],lists[1]);
 }
 int mid = lists.length/2;
 ListNode[] l1 = new ListNode[mid];
 for(int i = 0; i < mid; i++){
 l1[i] = lists[i];
 }
 ListNode[] l2 = new ListNode[lists.length-mid];
 for(int i = mid,j=0; i < lists.length; i++,j++){
 l2[j] = lists[i];
 }
 return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));
 }
 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 if (l1 == null) return l2;
 if (l2 == null) return l1;
 ListNode head = null;
 if (l1.val <= l2.val){
 head = l1;
 head.next = mergeTwoLists(l1.next, l2);
 } else {
 head = l2;
 head.next = mergeTwoLists(l1, l2.next);
 }
 return head;
 }
}

閱讀更多 五分鐘學算法 的文章

關鍵字: Java 算法 數據結構