23. 合并 K 个升序链表

题目描述

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]

输出：[1,1,2,3,4,4,5,6]

解释：链表数组如下： [

1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6

示例 2：

输入：lists = []

输出：[]

示例 3：

输入：lists = [[]]

输出：[]

题解

输入一个链表数组，数组中的每一个元素都是链表，并将所有的链表都合并为一个升序链表。

这个题目有多个解法，但是归根到底都是使用多次两两合并。

解法：

使用类似二分查找的方法，将数组一分为二，如此递归，直到分出的数组中只有一个或两个链表，然后进行两两合并。

如：lists=[x1, x2,…x(k/2-1), xk/2, …, xk-1, xk]

先将lists分为 [x1, x2,…x(k/2-1)] [ xk/2, …, xk-1, xk]

再对得到的两个新数组一分为二，直到得到：[x1, x2] [x3, x4]…[xk-1, xk ]

然后对其进行两两合并，如此递归得到最后的结果

代码：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }
    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
        	// 若数组只有一个元素，则直接返回该元素
            return lists[l];
        }
        if (l > r) {
        	// 若数组为空，则返回空
            return null;
        }
        // 除2取整, 拿到中间元素的索引
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val