Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
解题思路：
当时看到这个最开始的想法是两两进行合并然后这样不断循环下去，但是当时想说会不会复杂度有点高就没用了，就用了一种方法说，找到所有队列中的当前节点的最小值，取出添加到原节点的最后，让该节点指向其next，然后不断这样添加直到数组中只有一个非空节点。
[java] view plain copy print ? /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists(ListNode[] lists) { ListNode result = new ListNode(0); ListNode p = result; if(lists.length == 0) return null; else if(lists.length == 1) return lists[0]; int small1 = -1; int n = lists.length; for(int i = 0;i<lists.length;i++) { if(lists[i] == null) { n--; continue; } if(small1 <0 || lists[i].val < lists[small1].val) small1 = i; } if(small1 <0) return null; int small2 = findSecondSmallest(lists,small1); if(small2 < 0) return lists[small1]; while(n>0) { p.next = lists[small1]; lists[small1] = lists[small1].next; if(lists[small1] == null) { small1 = small2; small2 = findSecondSmallest(lists,small1); n--; } else if(lists[small1].val > lists[small2].val) { small1 = small2; small2 = findSecondSmallest(lists,small1); } p = p.next; if(n == 1) { p.next = lists[small1]; n--; } } return result.next; } public int findSecondSmallest(ListNode[] lists,int k) { int result = -1; for(int i = 0;i<lists.length;i++) { if(i == k || lists[i] == null) continue; if(result <0 || lists[i].val <lists[result].val) result = i; } return result; } } /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists(ListNode[] lists) { ListNode result = new ListNode(0); ListNode p = result; if(lists.length == 0) return null; else if(lists.length == 1) return lists[0]; int small1 = -1; int n = lists.length; for(int i = 0;i<lists.length;i++) { if(lists[i] == null) { n--; continue; } if(small1 <0 || lists[i].val < lists[small1].val) small1 = i; } if(small1 <0) return null; int small2 = findSecondSmallest(lists,small1); if(small2 < 0) return lists[small1]; while(n>0) { p.next = lists[small1]; lists[small1] = lists[small1].next; if(lists[small1] == null) { small1 = small2; small2 = findSecondSmallest(lists,small1); n--; } else if(lists[small1].val > lists[small2].val) { small1 = small2; small2 = findSecondSmallest(lists,small1); } p = p.next; if(n == 1) { p.next = lists[small1]; n--; } } return result.next; } public int findSecondSmallest(ListNode[] lists,int k) { int result = -1; for(int i = 0;i<lists.length;i++) { if(i == k || lists[i] == null) continue; if(result <0 || lists[i].val <lists[result].val) result = i; } return result; } }
结果就LTE了，因为当数组中有大量的短的链表的时候这样是很麻烦的。看了下别人的答案还真是用两两合并的，看来是我想多了...代码就用leetcode里面第三个答案的就好了，写的真的很不错。（My simple java Solution use recursion）。又学到了一种新技能。
[java] view plain copy print ? public static ListNode mergeKLists(ListNode[] lists){ return partion(lists,0,lists.length-1); } public static ListNode partion(ListNode[] lists,int s,int e){ if(s==e) return lists[s]; if(s<e){ int q=(s+e)/2; ListNode l1=partion(lists,s,q); ListNode l2=partion(lists,q+1,e); return merge(l1,l2); }else return null; } //This function is from Merge Two Sorted Lists. public static ListNode merge(ListNode l1,ListNode l2){ if(l1==null) return l2; if(l2==null) return l1; if(l1.val<l2.val){ l1.next=merge(l1.next,l2); return l1; }else{ l2.next=merge(l1,l2.next); return l2; } } public static ListNode mergeKLists(ListNode[] lists){ return partion(lists,0,lists.length-1); } public static ListNode partion(ListNode[] lists,int s,int e){ if(s==e) return lists[s]; if(s<e){ int q=(s+e)/2; ListNode l1=partion(lists,s,q); ListNode l2=partion(lists,q+1,e); return merge(l1,l2); }else return null; } //This function is from Merge Two Sorted Lists. public static ListNode merge(ListNode l1,ListNode l2){ if(l1==null) return l2; if(l2==null) return l1; if(l1.val<l2.val){ l1.next=merge(l1.next,l2); return l1; }else{ l2.next=merge(l1,l2.next); return l2; } }
