正文
LeetCode 23 Merge k Sorted Lists（合并k个有序链表）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
?xml version="1.0" encoding="UTF-8"? 题目链接： https://leetcode.com/problems/merge-k-sorted-lists/?tab=Description
?xml version="1.0" encoding="UTF-8"?
Problem： 给出k个有序的list, 将其进行合并得到一个有序的list
对于给出的ListNode[] lists ，可以进行两两合并。divide and conquer
将list分为前后两部分，对前半部分再次进行分半操作，对后半部分进行分半操作，
然后将其进行合并操作。
合并操作也就是对两个list进行合并
合并操作可以采用递归算法：当l1的值小于l2时，合并l1.next 和l2 返回 l1 ，对于l2同样如此
注意两条判断
if(l1==null) return l2;
if(l2==null) return l1;
这两条语句十分重要，因为当一个list为空，另一个不为空时，需要返回不为空的一个
在这里的merger函数 返回的究竟是l1呢还是l2呢，取决于l1的第一个元素和l2的第一个元素哪一个小。 哪一个小返回哪一个。
并且注意 l1或者在merger过程中一直指向list的头(改变的只是中间的连接)
参考代码：
package leetcode_50; /***
*
* @author pengfei_zheng
* 合并k个list
*/
public class Solution23 {
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public static ListNode mergeKLists(ListNode[] lists){
return partion(lists,0,lists.length-1);
} public static ListNode partion(ListNode[] lists,int s,int e){
if(s==e) return lists[s];
if(s<e){
int q=(s+e)/2;
ListNode l1=partion(lists,s,q);
ListNode l2=partion(lists,q+1,e);
return merge(l1,l2);
}else
return null;
} //This function is from Merge Two Sorted Lists.
public static ListNode merge(ListNode l1,ListNode l2){
if(l1==null) return l2;
if(l2==null) return l1;
if(l1.val<l2.val){
l1.next=merge(l1.next,l2);
return l1;
}else{
l2.next=merge(l1,l2.next);
return l2;
}
}
}
