leetcode oj java 23. Merge k Sorted Lists

Subscribe to see which companies asked this question

二、解决思路：

Merge k Sorted Lists 属于 Merge 2 Sorted Lists 的变种，Merge 2 Sorted Lists 的方法见：http://blog.csdn.net/u011060119/article/details/53899516

Merge k Sorted Lists 首先想到的是1和2merge , 再和3merge, merge的结果再和4merge....但是很慢。
我们考虑每次Merge 两个。在下图的示例中暂且以加法来表示Merge。
数组为： 0 1 2 3 4 5 6 7 8 9 10 11 12  每次合并两个并存入前一个，合并完成返回第一个即可。

三、代码：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
public class Solution {public static ListNode mergeLists(ListNode r1, ListNode r2) {if (r1 == null) {return r2;}if (r2 == null) {return r1;}ListNode phead = null;if (r1.val < r2.val) {phead = r1;phead.next = mergeLists(r1.next, r2);} else {phead = r2;phead.next = mergeLists(r1, r2.next);}return phead;}public ListNode mergeKLists(ListNode[] lists) {if (lists.length == 0) {return null;}if (lists.length == 1) {return lists[0];}int n = 2;;while (n < lists.length * 2) {for (int i = 0; i < lists.length; i += n) {if (i + n / 2 < lists.length) {lists[i] = mergeLists(lists[i], lists[i + n / 2]);}};n = n * 2;}return lists[0];}
}