Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
题目描述：归并排序k个有序单链表。（感觉LeetCode说到排序默认即是自然会顺序，数字递增，字母按顺序）
题目思路：
【超时思路】先说一个由二路归并得来的思维简单、看似取巧实则复杂度奇高的方法：直接k路归并。
1.内循环： 在lists指向的k个链表元素之间选出一个最小的lists[i]，链接到最终要输出的链表上去，再将lists[i]指向最小元素的下一个节点。
2.外循环：
循环上述过程直到lists都为空。
复杂度分析：假设有n个长度都为m的有序链表在归并，那么总的比较次数是多少呢？取出一个元素要比较n次，那么总共要经历O(n*n*m)次比较才可以完全归并。这复杂度交LeetCode上，妥妥的超时了。
超时代码：
class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class Solution { /** 思路简单，但是最坏复杂度很高的算法。比如n个单链表都只有一个元素，用该方法归并却需要n*n次大小比较，复杂度太高了 * @param lists * @return */ public ListNode mergeKLists(ListNode[] lists) { ListNode result=new ListNode(0),p=result; int k=0,min=0; while(true){ min=Integer.MAX_VALUE; k=-1; for(int i=0;i<lists.length;i++){ //每次都从lists[]所指向的头里挑出来一个最小的，加入有序单链表 if(lists[i]!=null && min>=lists[i].val){ //记录最小值和index位置 min=lists[i].val; k=i; } } if(k==-1){ //若在本轮查找中，没有进入比较环节，则所有链表都到头了，退出循环返回 p.next=null; break; }else{ p=p.next=lists[k]; lists[k]=lists[k].next; } } return result.next; } }
【AC思路】AC代码的思路本质也是建立在二路归并排序上的，即将lists的链表两两两路归并，最后得到最后的一路链表输出即可。粗略的看，整体复杂度最大不超过O(n2logn)。
import java.lang.Math; class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists.length>0){ //如果lists中的元素数在1一下，就不用归并了，直接输出就好 int Niterator=(int)Math.ceil(Math.log(lists.length)/Math.log(2)); //在lists中使用二路归并，要归并多少层（8进4视为一层，4进2视为一层）,做法就是log2(lists.length)再向上取整就行了 for(int i=1;i<=Niterator;i++){ int interval=(int)Math.pow(2, i); //对于不同的归并层，计算每个归并组的间隔，最底层2，上一层4，再上一层8，就这么来 for(int j=0;j+interval/2<lists.length;j+=interval){ lists[j]=mergeTwoLists(lists[j],lists[j+interval/2]); //在每一组内做二路归并，把结果给到这组的首个位置上保存，j+interval/2这个值的由来大家画个满二叉树体会一下就好了 } } return lists[0]; }else return null; } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //二路归并，O(N)复杂度，太简单啦 ListNode result=new ListNode(0),p=result,p1=l1,p2=l2; while(p1!=null&&p2!=null){ if(p1.val<p2.val){ p=p.next=p1; p1=p1.next; }else{ p=p.next=p2; p2=p2.next; } } p.next=(p1==null?p2:p1); //一个链表先耗尽，就把另一个接到已有序的链表末位 return result.next; } } public class Main{ public static void main(String[] args){ /*Scanner in=new Scanner(System.in); String target=in.nextLine();*/ ListNode[] lists=new ListNode[0]; for(int j=0;j<lists.length;j++){ lists[j]=new ListNode(1); ListNode temp=lists[j]; for(int i=2;i<=6;i++){ temp.next=new ListNode(i); temp=temp.next; } temp.next=null; } long startTime=System.currentTimeMillis(); Solution find=new Solution(); ListNode temp=find.mergeKLists(lists); long endTime=System.currentTimeMillis(); long excTime=(long)(endTime-startTime); System.out.println("执行时间："+excTime+"ms"); for(int i=0;temp!=null;i++){ System.out.println(temp.val); temp=temp.next; } } }
