题目描述
k个升序链表合并为一个新的升序链表。
示例：
输入：1->4->5, 1->3->4, 2->6
输出：1->1->2->3->4->4->5->6
解析
考察重点：分治算法和递归实现
分治算法把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。-----引用自维基百科
实现方法
- 分治算法，进行两两合并，k个升序链表合并可以看作多个两个升序链表的依次合并。把k个链表合并的问题拆解成多个两两链表合并的问题，大问题分成子问题。
- 递归实现k个升序链表的合并相当于第一个链表与k-1个链表合并结果的再合并。
实现技巧：
递归实现编码简单，性能消耗大；分治算法编码相对困难，效率高。
分治算法代码
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length <= 0){
return null;
}
if(lists.length == 1){
return lists[0];
}
int interval = 1;//遍历数组每次前进的间隔
while(interval < lists.length){//如果间隔小于数组长度继续遍历
/**从索引0开始，每次跳跃interval * 2遍历下一个元素。
并且i+interval要小于数组长度，这样合并的两个链表中的第二个链表存在。
for循环每次合并计算结果保存在索引是偶数的位置上，间隔依次为1，2，4，8....
最后一次合并后结果放置在索引0位置
*/
for(int i = 0; i < lists.length - interval; i = i + interval * 2){
lists[i] = merge2Lists(lists[i], lists[i + interval]);//合并i和i+interval的两个链表，并且结果赋值到i
}
interval = interval * 2;//间隔翻倍
}
return lists[0];//返回最后的结果
}
/*递归合并两个有序链表*/
private ListNode merge2Lists(ListNode l1, ListNode l2){
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
ListNode res;
if(l1.val < l2.val){
res = l1;
l1 = l1.next;
}else {
res = l2;
l2 = l2.next;
}
res.next = merge2Lists(l1, l2);
return res;
}
递归实现代码
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length <= 0){
return null;
}
if(lists.length == 1){//递归的结束条件
return lists[0];
}
/**这里做了一个优化，先合并前两个链表结果，再与k-2个链表结果合并，
比起第一个链表和k-1个链表结果合并效率更高，因为mergeKLists递归次数减少了*/
ListNode l1 = merge2Lists(lists[0], lists[1]);
ListNode[] lists2 = new ListNode[lists.length - 2];
System.arraycopy(lists, 2, lists2, 0, lists2.length);//赋值数组后k-2个元素
ListNode l2 = mergeKLists(lists2);//递归mergeKLists处理新的数组
return merge2Lists(l1, l2);//合并前两个链表结果与k-2个链表结果
}
/*递归合并两个有序链表*/
private ListNode merge2Lists(ListNode l1, ListNode l2){
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
ListNode res;
if(l1.val < l2.val){
res = l1;
l1 = l1.next;
}else {
res = l2;
l2 = l2.next;
}
res.next = merge2Lists(l1, l2);
return res;
}
总结
递归实现编码简单快捷在实际生产中大量使用，不过对于执行时间要求严格的需求开发不免要多用心寻找效率更高的算法。分治算法是算法设计中常用技巧需要重点掌握。
