一道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; } }