本文首是圖解 LeetCode 系列文章之一。

個(gè)人網(wǎng)站：https://www.cxyxiaowu.com

題目來(lái)源于 LeetCode 上第 23 號(hào)問(wèn)題：合并 K 個(gè)排序鏈表。題目難度為 Hard，目前通過(guò)率為 45.8% 。

題目描述

合并 k 個(gè)排序鏈表，返回合并后的排序鏈表。請(qǐng)分析和描述算法的復(fù)雜度。

示例:

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


輸入

輸出

題目解析

題目分析一

這里需要將這 k 個(gè)排序鏈表整合成一個(gè)排序鏈表，也就是說(shuō)有多個(gè)輸入，一個(gè)輸出，類(lèi)似于漏斗一樣的概念。

因此，可以利用最小堆的概念。如果你對(duì)堆的概念不熟悉，可以戳這先了解一下~

取每個(gè) Linked List 的最小節(jié)點(diǎn)放入一個(gè) heap 中，排序成最小堆。然后取出堆頂最小的元素，放入輸出的合并 List 中，然后將該節(jié)點(diǎn)在其對(duì)應(yīng)的 List 中的下一個(gè)節(jié)點(diǎn)插入到 heap 中，循環(huán)上面步驟，以此類(lèi)推直到全部節(jié)點(diǎn)都經(jīng)過(guò) heap。

由于 heap 的大小為始終為 k ，而每次插入的復(fù)雜度是 logk ，一共插入了 nk 個(gè)節(jié)點(diǎn)。時(shí)間復(fù)雜度為 O(nklogk)，空間復(fù)雜度為O(k)。

動(dòng)畫(huà)演示

代碼實(shí)現(xiàn)

class?Solution?{
????public?ListNode?mergeKLists(ListNode[]?lists)?{
????????//用heap(堆)這種數(shù)據(jù)結(jié)構(gòu)，也就是?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;
????}
}


題目分析二

這道題需要合并 k 個(gè)有序鏈表，并且最終合并出來(lái)的結(jié)果也必須是有序的。如果一開(kāi)始沒(méi)有頭緒的話(huà)，可以先從簡(jiǎn)單的開(kāi)始：合并 兩 個(gè)有序鏈表。

合并兩個(gè)有序鏈表：將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例：

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


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

所以代碼實(shí)現(xiàn)很容易寫(xiě)：

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;
????????????}
????????}
????????//?注意點(diǎn)：當(dāng)有鏈表為空時(shí)，直接連接另一條鏈表
????????if?(l1?==?null)?{
????????????cur.next?=?l2;
????????}?else?{
????????????cur.next?=?l1;
????????}
????????return?dummyHead.next;
????}


現(xiàn)在回到一開(kāi)始的題目：合并 K 個(gè)排序鏈表。

合并 K 個(gè)排序鏈表 與 合并兩個(gè)有序鏈表 的區(qū)別點(diǎn)在于操作有序鏈表的數(shù)量上，因此完全可以按照上面的代碼思路來(lái)實(shí)現(xiàn)合并 K 個(gè)排序鏈表。

這里可以參考 **歸并排序 **的分治思想，將這 ?K 個(gè)鏈表先劃分為兩個(gè) K/2 個(gè)鏈表，處理它們的合并，然后不停的往下劃分，直到劃分成只有一個(gè)或兩個(gè)鏈表的任務(wù)，開(kāi)始合并。

代碼實(shí)現(xiàn)

根據(jù)上面的動(dòng)畫(huà)，實(shí)現(xiàn)代碼非常簡(jiǎn)單也容易理解，先劃分，直到不能劃分下去，然后開(kāi)始合并。

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;
????}
}