文章目錄

• 題目描述
• 解法 & 代碼
• • • 二刷

沖的第一道hard，好耶！

題目描述

• 這道題和前面的合并兩個有序鏈表很有聯系。直接調用了整個合并函數。
• 可以看成我們已經有了足夠優秀的“兩條鏈表合并“的函數，然后考慮對K條鏈表如何進行合并分配。
• 結構類似歸并排序噢～
  

解法 & 代碼

• 對K條鏈表，用一個merge不斷二分；當merge只有兩條時，進行twoList合并操作。只有一條時，直接返回當前鏈表。（這也解決了在二分時出現奇數的問題
• 之前考慮過不用merge，直接for循環一次合并入一條，也能過，但是復雜度會到O((m+n)*k)。

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/ class Solution {public ListNode mergeKLists(ListNode[] lists) {// 數組空的情況，和數組為null的情況if(lists == null || lists.length == 0){return null;}return merge(lists, 0, lists.length - 1);}// 遞歸進行合并操作，復雜度log(n)public ListNode merge(ListNode[] lists, int left, int right){// 數組就一條鏈表的情況 && if (left == right)return lists[left];// 返回左、右兩部分數組鏈表的兩個結果，然后進行鏈表的兩兩合并twoList();return twoList(merge(lists,left, (right + left) / 2), merge(lists, (right + left) / 2 + 1, right));}// 放入兩條鏈表，返回一條合并鏈表// 時間復雜度O(m+n)public ListNode twoList(ListNode l1, ListNode l2) {// 有鏈表為空的情況if(l1 == null)return l2;if(l2 == null)return l1;else if(l1.val < l2.val) {l1.next = twoList(l1.next,l2);return l1;}else {l2.next = twoList(l2.next,l1);return l2;}} }

• 時間復雜度O((m+n)*log(k))，也就是兩鏈表合并的復雜度乘上K鏈表合并的復雜度
• 空間復雜度O(1)

二刷

• 這道題怎么樣都是爆殺…hard友好題！

class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists == null || lists.length == 0) return null;return merge(lists, 0, lists.length - 1);}ListNode merge(ListNode[] lists, int left, int right) {if(left == right) return lists[left];if(left + 1 == right) return mergeTwoLists(lists[left], lists[right]);int mid = (left + right) / 2;return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));}ListNode mergeTwoLists(ListNode head1, ListNode head2) {if(head1 == null) return head2;if(head2 == null) return head1;if(head1.val < head2.val) {head1.next = mergeTwoLists(head1.next, head2);return head1;} else {head2.next =mergeTwoLists(head1, head2.next);return head2;}} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】23.合并K个升序列表（Java、分治、链表）的全部內容，希望文章能夠幫你解決所遇到的問題。

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