<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 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">``` <span class="hljs-title">/* * @lc app=leetcode id=23 lang=javascript * * [23] Merge k Sorted Lists * * https://leetcode.com/problems/merge-k-sorted-lists/description/ * */</span> <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">mergeTwoLists</span>(<span class="hljs-params">l1, l2</span>) </span>{ <span class="hljs-keyword">const</span> dummyHead = {}; <span class="hljs-keyword">let</span> current = dummyHead; <span class="hljs-title">// l1: 1 -> 3 -> 5</span> <span class="hljs-title">// l2: 2 -> 4 -> 6</span> <span class="hljs-keyword">while</span> (l1 !== <span class="hljs-params">null</span> && l2 !== <span class="hljs-params">null</span>) { <span class="hljs-keyword">if</span> (l1.val < l2.val) { current.next = l1; <span class="hljs-title">// 把小的添加到結果鏈表</span> current = current.next; <span class="hljs-title">// 移動結果鏈表的指針</span> l1 = l1.next; <span class="hljs-title">// 移動小的那個鏈表的指針</span> } <span class="hljs-keyword">else</span> { current.next = l2; current = current.next; l2 = l2.next; } } <span class="hljs-keyword">if</span> (l1 === <span class="hljs-params">null</span>) { current.next = l2; } <span class="hljs-keyword">else</span> { current.next = l1; } <span class="hljs-keyword">return</span> dummyHead.next; } <span class="hljs-title">/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */</span> <span class="hljs-title">/** * @param {ListNode[]} lists * @return {ListNode} */</span> <span class="hljs-keyword">var</span> mergeKLists = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">lists</span>) </span>{ <span class="hljs-title">// 圖參考: https://zhuanlan.zhihu.com/p/61796021</span> <span class="hljs-keyword">if</span> (lists.length === <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">null</span>; <span class="hljs-keyword">if</span> (lists.length === <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> lists[<span class="hljs-params">0</span>]; <span class="hljs-keyword">if</span> (lists.length === <span class="hljs-params">2</span>) { <span class="hljs-keyword">return</span> mergeTwoLists(lists[<span class="hljs-params">0</span>], lists[<span class="hljs-params">1</span>]); } <span class="hljs-keyword">const</span> mid = lists.length >> <span class="hljs-params">1</span>; <span class="hljs-keyword">const</span> l1 = []; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < mid; i++) { l1[i] = lists[i]; } <span class="hljs-keyword">const</span> l2 = []; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = mid, j = <span class="hljs-params">0</span>; i < lists.length; i++, j++) { l2[j] = lists[i]; } <span class="hljs-keyword">return</span> mergeTwoLists(mergeKLists(l1), mergeKLists(l2)); }; ``` ``` Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-title"># Definition for singly-linked list.</span> <span class="hljs-title"># class ListNode:</span> <span class="hljs-title"># def __init__(self, x):</span> <span class="hljs-title"># self.val = x</span> <span class="hljs-title"># self.next = None</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">mergeKLists</span><span class="hljs-params">(self, lists: List[ListNode])</span> -> ListNode:</span> n = len(lists) <span class="hljs-title"># basic cases</span> <span class="hljs-keyword">if</span> lenth == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-keyword">None</span> <span class="hljs-keyword">if</span> lenth == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> lists[<span class="hljs-params">0</span>] <span class="hljs-keyword">if</span> lenth == <span class="hljs-params">2</span>: <span class="hljs-keyword">return</span> self.mergeTwoLists(lists[<span class="hljs-params">0</span>], lists[<span class="hljs-params">1</span>]) <span class="hljs-title"># divide and conqure if not basic cases</span> mid = n // <span class="hljs-params">2</span> <span class="hljs-keyword">return</span> self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:n])) <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">mergeTwoLists</span><span class="hljs-params">(self, l1: ListNode, l2: ListNode)</span> -> ListNode:</span> res = ListNode(<span class="hljs-params">0</span>) c1, c2, c3 = l1, l2, res <span class="hljs-keyword">while</span> c1 <span class="hljs-keyword">or</span> c2: <span class="hljs-keyword">if</span> c1 <span class="hljs-keyword">and</span> c2: <span class="hljs-keyword">if</span> c1.val < c2.val: c3.next = ListNode(c1.val) c1 = c1.next <span class="hljs-keyword">else</span>: c3.next = ListNode(c2.val) c2 = c2.next c3 = c3.next <span class="hljs-keyword">elif</span> c1: c3.next = c1 <span class="hljs-keyword">break</span> <span class="hljs-keyword">else</span>: c3.next = c2 <span class="hljs-keyword">break</span> <span class="hljs-keyword">return</span> 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)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看