一道hard题，首先用的这个递归的方法，确实很难一次想到，基本只能看了一遍后好好理解，再记忆。
记忆思路：
1，有了merge2Lists的方法，是一个可以利用的基础。merge2Lists：点击打开链接
2，利用这个融合2个list的方法，把一个长的list array，通过分治的思路，切成两半，这个两半都抽象成一个ListNode通过递归调用函数本身，找到递归点，然后通过merge2List，合并后即可return。。。还有一个关键点就是这个递归的退出条件是什么？那就是当指向一个list时，就返回这个list，这是不是相当于merge2Lists中的 null的情况！！当只有一个list时，就return这个list，在merge2Lists是的判断条件是 另一个为null，而在这里的判断条件就是 left==right，本质都是一样的，只剩下一个list了！这个分析是不是很透彻很本质，建立不同题目之间的联系。
代码如下：
/** * 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) { int len=lists.length; return len==0?null:partition(lists, 0, len-1); } private ListNode partition(ListNode[] lists, int left, int right){ if(left==right) return lists[left]; if(left<right){ int mid= left+(right-left)/2; ListNode l1=partition(lists, left, mid); ListNode l2=partition(lists, mid+1, right); return merge2Lists(l1, l2); } else return null; } private ListNode merge2Lists(ListNode l1, ListNode l2){ if(l1==null) return l2; if(l2==null) return l1; ListNode mergeNode; if(l1.val<l2.val){ mergeNode=l1; mergeNode.next=merge2Lists(l1.next, l2); } else{ mergeNode=l2; mergeNode.next=merge2Lists(l1, l2.next); } return mergeNode; } } 另一个方法是通过PriorityQueue的方式，因为PQ只对基本类型int等进行默认排序，那么要对其他的自定义的data structure进行排序，那就要进行method override，这是第一步！有了这个一步之后，相当生成了一个对ListNode的排序器，可以把每个list都加入PQ，自然排序完成了，接着从头poll，再把poll出来的node的nextNode加入PQ如果不为null的话。就是这个一个思路，用来记忆，剩下的就是实现了。其中PQ的override是件利器啊！实习面试fb时已经面过，suntianhang面试时也有关于坐标的struct，也可以用PQ，SO必须背下来。 /** * 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) { if(lists.length==0) return null; PriorityQueue<ListNode> PQ = new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>(){ @Override public int compare(ListNode l1, ListNode l2){ if(l1.val<l2.val) return -1; else if(l1.val==l2.val) return 0; else return 1; } }); //看看这个PriorityQueue的ctor是怎么写的！在平时new Class()的括号内部加了两个参数，就是两个parameter的的ctor，第一个是size，第二个有是一个新的class Comparator<ListNode>()也是有无参的ctor，但是要重载其中的函数，来针对ListNode，那就要有函数体{}，这个{}里就是重载一个public int compare(Type t1, Type t2){...} , 这里的...代表就是三个t1,t2的比较大小的情况和对应的反回值。 // 有了这个PQ后，就先加入每个listNode，记得PQ的方法是 add() + poll()，加入和选举，不是pushback哦，因为不是加在后面，不知道是加到哪里，而poll代表的是要选举出一个最小的意思。 for(ListNode listNode: lists){ if(listNode!=null) PQ.add(listNode); } // 常规的建立一个新list的方法：new dummy， curr=dummy， 连接curr移动curr，最后return curr.next; ListNode dummy= new ListNode(0); ListNode curr=dummy; while(!PQ.isEmpty()){ curr.next=PQ.poll(); curr=curr.next; if(curr.next!=null) PQ.add(curr.next); } return dummy.next; } }