0023. 合并K個升序鏈表 · ttttt

# 0023. 合并K個升序鏈表 ## 題目地址（23. 合并 K 個排序鏈表） <https://leetcode-cn.com/problems/merge-k-sorted-lists/> ## 題目描述 ``` <pre class="calibre18">``` 合并 k 個排序鏈表，返回合并后的排序鏈表。請分析和描述算法的復雜度。示例: 輸入: [ 1->4->5, 1->3->4, 2->6 ] 輸出: 1->1->2->3->4->4->5->6 ``` ``` ## 前置知識 - 鏈表 - 歸并排序 ## 公司 - 阿里 - 百度 - 騰訊 - 字節 ## 思路這道題目是合并 k 個已排序的鏈表，號稱 leetcode 目前`最難`的鏈表題。和之前我們解決的[88.merge-sorted-array](88.merge-sorted-array.html)很像。他們有兩點區別： 1. 這道題的數據結構是鏈表，那道是數組。這個其實不復雜，畢竟都是線性的數據結構。 2. 這道題需要合并 k 個元素，那道則只需要合并兩個。這個是兩題的關鍵差別，也是這道題難度為`hard`的原因。因此我們可以看出，這道題目是`88.merge-sorted-array`的進階版本。其實思路也有點像，我們來具體分析下第二條。如果你熟悉合并排序的話，你會發現它就是`合并排序的一部分`。具體我們可以來看一個動畫 ![](https://img.kancloud.cn/f4/81/f48141d451b4abfb55fdb3664a183c92_600x334.gif) （動畫來自 <https://zhuanlan.zhihu.com/p/61796021> ） ## 關鍵點解析 - 分治 - 歸并排序(merge sort) ## 代碼代碼支持 JavaScript， Python3 JavaScript Code： ``` <pre class="calibre18">``` /* * @lc app=leetcode id=23 lang=javascript * * [23] Merge k Sorted Lists * * https://leetcode.com/problems/merge-k-sorted-lists/description/ * */ function mergeTwoLists(l1, l2) { const dummyHead = {}; let current = dummyHead; // l1: 1 -> 3 -> 5 // l2: 2 -> 4 -> 6 while (l1 !== null && l2 !== null) { if (l1.val < l2.val) { current.next = l1; // 把小的添加到結果鏈表 current = current.next; // 移動結果鏈表的指針 l1 = l1.next; // 移動小的那個鏈表的指針 } else { current.next = l2; current = current.next; l2 = l2.next; } } if (l1 === null) { current.next = l2; } else { current.next = l1; } return dummyHead.next; } /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode[]} lists * @return {ListNode} */ var mergeKLists = function (lists) { // 圖參考： https://zhuanlan.zhihu.com/p/61796021 if (lists.length === 0) return null; if (lists.length === 1) return lists[0]; if (lists.length === 2) { return mergeTwoLists(lists[0], lists[1]); } const mid = lists.length >> 1; const l1 = []; for (let i = 0; i < mid; i++) { l1[i] = lists[i]; } const l2 = []; for (let i = mid, j = 0; i < lists.length; i++, j++) { l2[j] = lists[i]; } return mergeTwoLists(mergeKLists(l1), mergeKLists(l2)); }; ``` ``` Python3 Code： ``` <pre class="calibre18">``` # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: n = len(lists) # basic cases if lenth == 0: return None if lenth == 1: return lists[0] if lenth == 2: return self.mergeTwoLists(lists[0], lists[1]) # divide and conqure if not basic cases mid = n // 2 return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:n])) def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: res = ListNode(0) c1, c2, c3 = l1, l2, res while c1 or c2: if c1 and c2: if c1.val < c2.val: c3.next = ListNode(c1.val) c1 = c1.next else: c3.next = ListNode(c2.val) c2 = c2.next c3 = c3.next elif c1: c3.next = c1 break else: c3.next = c2 break return res.next ``` ``` **復雜度分析** - 時間復雜度：O(kn?logk)O(kn\*logk)O(kn?logk) - 空間復雜度：O(logk)O(logk)O(logk) ## 相關題目 - [88.merge-sorted-array](88.merge-sorted-array.html) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)