k 个有序链表的合并。
我们用 N 表示链表的总长度，考虑最坏情况，k 个链表的长度相等，都为 n 。
解法一 暴力破解
简单粗暴，遍历所有的链表，将数字存到一个数组里，然后用快速排序，最后再将排序好的数组存到一个链表里。
publicListNodemergeKLists(ListNode[] lists) { List<Integer>l=newArrayList<Integer>(); //存到数组for (ListNodeln : lists) { while (ln!=null) { l.add(ln.val); ln=ln.next; } } //数组排序Collections.sort(l); //存到链表ListNodehead=newListNode(0); ListNodeh=head; for (inti : l) { ListNodet=newListNode(i); h.next=t; h=h.next; } h.next=null; returnhead.next; }
时间复杂度：假设 N 是所有的数字个数，存到数组是 O（N），排序如果是用快速排序就是 O(Nlog_N)O(NlogN) ，存到链表是 O（N），所以取个最大的，就是 O(Nlog_N)O(NlogN)。
空间复杂度：新建了一个链表，O（N）。
解法二 一列一列比较
我们可以一列一列的比较，将最小的一个存到一个新的链表里。
publicListNodemergeKLists(ListNode[] lists) { intmin_index=0; ListNodehead=newListNode(0); ListNodeh=head; while (true) { booleanisBreak=true;//标记是否遍历完所有链表intmin=Integer.MAX_VALUE; for (inti=0; i<lists.length; i++) { if (lists[i] !=null) { //找出最小下标if (lists[i].val<min) { min_index=i; min=lists[i].val; } //存在一个链表不为空，标记改完 falseisBreak=false; } } if (isBreak) { break; } //加到新链表中ListNodea=newListNode(lists[min_index].val); h.next=a; h=h.next; //链表后移一个元素lists[min_index] =lists[min_index].next; } h.next=null; returnhead.next; }
时间复杂度：假设最长的链表长度是 n ，那么 while 循环将循环 n 次。假设链表列表里有 k 个链表，for 循环执行 k 次，所以时间复杂度是 O（kn）。
空间复杂度：N 表示最终链表的长度，则为 O（N）。
总
优先队列的运用印象深刻，此外对两两链表的合并，我们仅仅改变了合并的方式就将时间复杂度降低了很多，美妙！
