[LeetCode]合并K个排序链表（Merge k Sorted Lists）

共计 643 个字符，预计需要花费 2 分钟才能阅读完成。

题目描述
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:[1->4->5, 1->3->4, 2->6] 输出: 1->1->2->3->4->4->5->6
ListNode 数据结构
class ListNode {
int val;
ListNode next;

ListNode(int x) {
val = x;
}
}
解决方法
相邻链表两两合并，两两合并详情见合并两个有序链表
public ListNode mergeKLists(ListNode[] lists) {
int interval = 1;

while (interval < lists.length) {
for (int i = 0; i < lists.length – interval; i += interval * 2) {
lists[i] = merge2Lists(lists[i], lists[i + interval]);
}
interval *= 2;
}

return lists.length > 0 ? lists[0] : null;
}

public ListNode merge2Lists(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
if (l2 == null)
return l1;
if (l1.val < l2.val) {
l1.next = merge2Lists(l1.next, l2);
return l1;
} else {
l2.next = merge2Lists(l1, l2.next);
return l2;
}
}
时间复杂度：O(Nlogk)，k 是链表的数目