---

Time：2019/4/10
Title: Merge K Sorted Lists
Difficulty: Difficulty
Author: 小鹿

---

題目：Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

合并?k?個排序鏈表，返回合并后的排序鏈表。請分析和描述算法的復雜度。

Example:

Input: [1->4->5,1->3->4,2->6 ] Output: 1->1->2->3->4->4->5->6 復制代碼

Solve:

▉ 算法思路

如果我們完成了簡單的基于兩個單鏈表的合并之后，對于這個題來說，考察點是分治算法，我認為還有一個考察點就是遞歸調用，分治的同時經常用遞歸來解決。

1、本道題可以借助歸并排序的思想，稍加改造就可以解決。

2、將數組中的鏈表分治，就是不斷的將數組中的鏈表中間劃分，分別合并，然后整體合并成一個大鏈表。

▉ 代碼實現

/*** @param {number[]} nums* @return {number[]}* 功能：合并 k 個鏈表* 邊界條件：* 1）判斷數組是否為空* 2）判斷數組長度為 1 時* 3）判斷數組長度為 2 時* 4）判斷數組長度大于 2 時*/ var mergeKLists = function(lists) {// 當 lists 中有一個鏈表時if(lists.length == 0){return null;}else if(lists.length == 1){// 判斷數組長度為 1 時return lists[0];}else if(lists.length == 2){// 判斷數組長度為 2 時return mergeTwoLists(lists[0],lists[1]);}else{// 判斷數組長度大于 2 時// 取數組的中部坐標let middle = Math.floor(lists.length/2);// 取左右兩邊數組let leftList = lists.slice(0,middle);let rightList = lists.slice(middle);// 遞歸、分割、合并return mergeTwoLists(mergeKLists(leftList),mergeKLists(rightList));} }; //兩個鏈表合并 var mergeTwoLists = function(l1, l2) {let result = null;//終止條件if(l1 == null) return l2;if(l2 == null) return l1;//判斷數值大小遞歸if(l1.val < l2.val){result = l1;result.next = mergeTwoLists(l1.next,l2);}else{result = l2;result.next = mergeTwoLists(l2.next,l1);}//返回結果return result; }; 復制代碼

▉ 擴展：分治算法

分治算法經常和遞歸一塊使用，所謂分治算法，顧名思義，分而治之，最基本的分之算法在歸并排序、快速排序都有用到。也就是將原問題劃分成 n 個規模較小，并且結構與原問題相似的子問題，遞歸地解決這些子問題，然后再合并其結果，就得到原問題的解。

1、分治算法遞歸每層操作

• 分解：將原問題分解成一系列的子問題。
• 解決：遞歸地求解各個子問題，若子問題足夠小，則直接求解；
• 合并：將子問題的結果合并成原問題。

2、分治算法滿足的條件

• 可分解：原問題與分解成的小問題具有相同的模式；
• 無關聯：原問題分解成的子問題可以獨立求解，子問題之間沒有相關性，這一點是分治算法跟動態規劃的明顯區別。
• 終止條件：具有分解終止條件；
• 合并不能太復雜：可以將子問題合并成原問題，而這個合并操作的復雜度不能太高，否則就起不到減小算法總體復雜度的效果了。

---

歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！ Github：https://github.com/luxiangqiang/JS-LeetCode

---

歡迎關注我個人公眾號：「一個不甘平凡的碼農」，記錄了自己一路自學編程的故事。

總結

以上是生活随笔為你收集整理的LeetCode 之 JavaScript 解答第23题 —— 合并K个有序链表（Merge K Sorted Lists）的全部內容，希望文章能夠幫你解決所遇到的問題。

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