合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6
//迭代算法
public ListNode mergeKLists(ListNode[] lists) { if(lists==null||lists.length<1) { return null; } if(lists.length==1) { return lists[0]; } ListNode[] lists1=Arrays.copyOfRange(lists, 0, lists.length/2); ListNode[] lists2=Arrays.copyOfRange(lists, lists.length/2, lists.length); ListNode l1=mergeKLists(lists1); ListNode l2=mergeKLists(lists2); return merge(l1,l2); } private ListNode merge(ListNode l1, ListNode l2) { ListNode head=new ListNode(0); ListNode l=head; while(l1!=null||l2!=null) { if(l1==null) { l.next=l2; break; } if(l2==null) { l.next=l1; break; } if(l1.val>l2.val) { l.next=l2; l=l2; l2=l2.next; }else { l.next=l1; l=l1; l1=l1.next; } } return head.next; }
//这个方法简单 但是稍慢一点 而且有个Arrays.asList需要注意 得到的是AbstracList
public ListNode mergeKLists(ListNode[] lists) { ListNode res=new ListNode(0); ListNode p=res; /* * 这里得到的List是一个AbstractList，不支持增删改操作。 * 该AbstracList之四号简单地在已有的元素组上套了一层List 的接口， 所以不支持增删改操作 */ List<ListNode> t=Arrays.asList(lists); List<ListNode> l=new ArrayList<>(t); while(!l.isEmpty()) { ListNode min=l.get(0); for(ListNode node : l) { if(min.val>node.val) { min=node; } } p.next=min; p=p.next; l.remove(min); if(min.next!=null) { l.add(min.next); } } return res.next; }
