首页 > 代码库 > [leetcode]Merge k Sorted Lists
[leetcode]Merge k Sorted Lists
Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
这道题，第一次刷是过了，第二次同样的代码超时了，看来case是在不断加强的
算法
思路1：
最土的算法，两个月前能过，现在TLE，同[leetcode]Merge Two Sorted Lists，
首先把l1和l2合并到l1中，遍历2n个节点
再把合并之后的l1和l3合并到l1中，遍历3n个节点
再把合并之后的l1和l4合并到l1中，遍历4n个节点
....
最后把合并后的l1和lm合并到l1中，遍历m*n个节点
总共遍历了（2+3+...+m）*n个节点，时间复杂度为O(n*m^2)
代码如下：
1 public ListNode mergeKLists(List<ListNode> lists) { 2 if(lists == null || lists.size() == 0) return null; 3 ListNode l1 = lists.get(0); 4 for(int i = 1; i < lists.size(); i++) 5 l1 = mergeTwoLists(l1,lists.get(i)); 6 return l1; 7 } 8 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 9 if(l1 == null) return l2;10 if(l2 == null) return l1;11 ListNode head = new ListNode(1);12 head.next = l1;13 ListNode pre = head;14 ListNode node = l2;15 while(l2 != null){16 node = l2;17 while(pre.next != null && pre.next.val <= node.val){18 pre = pre.next;19 }20 l2 = node.next;21 node.next = pre.next;22 pre.next = node;23 pre = node;24 }25 return head.next;26 }
思路2：
分治法，将m个list分成两拨list1,list2，对每一拨分别处理
当list.size() = 1时，直接返回， size() = 2时候，即：merge2ListNode
处理完list1 和list2之后，再把二者合并
时间负责度O(n*klogk)【其中k为list.size()】
代码如下：
1 public class Solution { 2 public ListNode mergeKLists(List<ListNode> lists) { 3 if(lists == null || lists.size() == 0) return null; 4 if(lists.size() == 1) return lists.get(0); 5 if(lists.size() == 2){ 6 return merge2List(lists.get(0), lists.get(1)); 7 } 8 List<ListNode> l1 = new ArrayList<ListNode>(); 9 List<ListNode> l2 = new ArrayList<ListNode>();10 for(int i = 0;i < lists.size() ; i++){11 if(i < lists.size() / 2) l1.add(lists.get(i));12 else l2.add(lists.get(i));13 }14 ListNode list1 = mergeKLists(l1);15 ListNode list2 = mergeKLists(l2);16 return merge2List(list1, list2);17 }18 private ListNode merge2List(ListNode l1,ListNode l2){19 ListNode head = new ListNode(1);20 head.next = l1;21 ListNode pre = head;22 ListNode node = l2;23 while(l2 != null){24 node = l2;25 while(pre.next != null && pre.next.val <= node.val){26 pre = pre.next;27 }28 l2 = node.next;29 node.next = pre.next;30 pre.next = node;31 pre = node;32 }33 return head.next;34 }35 }
思路3：
堆，由于对堆不熟悉，所以写出来的代码很丑，不过好歹AC了，时间复杂度同分治法，明天过来再优化一下：
渣代码如下：
1 public class Solution { 2 public ListNode mergeKLists(List<ListNode> lists) { 3 if(lists == null || lists.size() == 0) return null; 4 int k = 0; 5 List<ListNode> list = new ArrayList<ListNode>(); 6 for(int i = 0; i < lists.size(); i++){ 7 if(lists.get(i) != null) { 8 k++; 9 list.add(lists.get(i));10 }11 }12 if(k == 0) return null;13 if(k == 1) return list.get(0);14 ListNode[] heap = new ListNode[k];15 for(int i = 0 ; i < k ; heap[i] = list.get(i),i++);16 for(int i = k / 2 - 1; i >= 0; i--){17 adjustHeap(heap, k, i);18 }19 ListNode result = new ListNode(0);20 ListNode tail = result;21 while(true){22 if(heap[0] == null){23 heap[0] = heap[k - 1];24 k--;25 }26 adjustHeap(heap, k, 0);27 tail.next = heap[0];28 if(k == 0) break;29 heap[0] = heap[0].next;30 tail = tail.next;31 }32 return result.next;33 }34 private void adjustHeap(ListNode[] heap,int size,int i){35 while( 2 * i + 1 < size ){36 ListNode left = heap[2 * i + 1];37 if(left == null) return;38 if(2 * i + 2 < size){39 ListNode right = heap[2 * i + 2];40 if(right.val <= left.val && right.val < heap[i].val){41 ListNode tem = right;42 heap[2 * i + 2] = heap[i];43 heap[i] = tem;44 i = 2 * i + 2;45 }else if(left.val <= right.val && left.val < heap[i].val){46 ListNode tem = left;47 heap[2 * i + 1] = heap[i];48 heap[i] = tem;49 i = 2 * i + 1;50 }else return;51 }else{52 if(left.val < heap[i].val){53 ListNode tem = left;54 heap[2 * i + 1] = heap[i];55 heap[i] = tem;56 }57 return;58 }59 }60 }61 62 }
参考资料：
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。