https://oj.leetcode.com/problems/merge-k-sorted-lists/
歸并K已經(jīng)整理陣列，和分析算法的復(fù)雜。

解決報(bào)告：無(wú)論是不考慮優(yōu)化，最簡(jiǎn)單的實(shí)現(xiàn)是要重新走路List<ListNode>。對(duì)當(dāng)中每一個(gè)鏈表同當(dāng)前鏈表做一遍類似于歸并排序最后一步的merge操作。
算法復(fù)雜度是O(KN)

public class Solution {ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode head = new ListNode(-1);ListNode current = head;while(list1!=null&&list2!=null) {if(list1.val<list2.val) {current.next = list1;list1 = list1.next;} else {current.next = list2;list2 = list2.next;}current = current.next;}if(list1!=null) {current.next = list1;} else {current.next = list2;}return head.next;}public ListNode mergeKLists(List<ListNode> lists) {if(lists==null||lists.size()==0) {return null;}ListNode head = lists.get(0);for(int i=1;i<lists.size();i++) {head = mergeTwoLists(head, lists.get(i));}return head;} }
上面的方法TLE了，上網(wǎng)查了一下注意到通過(guò)使用歸并排序算法可將鏈表排序的時(shí)間復(fù)雜度縮減到的O(NlgN)。詳細(xì)的計(jì)算公式就是：

所以借鑒歸并排序的方法，自頂向下，先遞歸的對(duì)鏈表的前半部分和后半部分進(jìn)行歸并排序，最后再merge。
下面代碼順利AC了，時(shí)間復(fù)雜度為：O(NlogK)

public class Solution {ListNode merge2Lists(ListNode list1, ListNode list2) {ListNode head = new ListNode(-1);ListNode current = head;while(list1!=null&&list2!=null) {if(list1.val<list2.val) {current.next = list1;list1 = list1.next;} else {current.next = list2;list2 = list2.next;}current = current.next;}if(list1!=null) {current.next = list1;} else {current.next = list2;}return head.next;}public ListNode mergeKLists(List<ListNode> lists) {if(lists==null||lists.size()==0) {return null;}if(lists.size()==1) {return lists.get(0);}int length = lists.size() ;int mid = (length - 1)/2 ;ListNode l1 = mergeKLists(lists.subList(0,mid + 1)) ;ListNode l2 = mergeKLists(lists.subList(mid + 1,length)) ;return merge2Lists(l1,l2) ;} }

版權(quán)聲明：本文博主原創(chuàng)文章，博客，未經(jīng)同意不得轉(zhuǎn)載。

總結(jié)

以上是生活随笔為你收集整理的LeetCode Merge k Sorted Lists 解决报告的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。