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

题目描述合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例:输入:[ 1->4->5, 1->3->4, 2->6]输出: 1->1->2->3->4->4->5->6ListNode数据结构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是链表的数目