力扣热题100题-合并 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 = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-k-sorted-lists

解答1：使用小顶堆

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    //第一种解法:需要将链表的节点放入到小顶堆中 
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length,new Comparator<ListNode>(){
            public int compare(ListNode o1, ListNode o2) {
                //由于是小顶堆，所以需要对比o1和o2的值的大小，如果
                if(o1.val < o2.val){
                    return -1;
                }
                if(o2.val < o1.val){
                    return 1;
                }
                return 0;
            }
        });
        for(ListNode temp: lists){
            queue.add(temp);
        }
        //设置返回信息的参数
        ListNode result = new ListNode(0);
        ListNode current = result;
        while(!queue.isEmpty()){
           ListNode temp = queue.poll();
           current.next = temp;
           if(temp.next != null){
               queue.add(temp.next);
           }
           current = current.next;
        }
        return result.next;
    }
}

解答2：分治算法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    //第二种解法：
    //链表两两合并，递归转化为两个升序链表合并
    // 如果左右边界相等直接返回左边界
    // 选取中间点，开始对中间点左右进行递归升序，转换为两个链表 分
    // 对上面递归后的两个结果进行递归合并
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        return merge(lists,0,lists.length -1);
        
    }

    /**对数组进行二分操作
     */
    public ListNode merge(ListNode[] lists,int left,int right){
        if(left == right){
            return lists[left];
        }
        //求数组的中间值
        int mid = left + (right - left) / 2;
        //找到左边的merge结果
        ListNode l1 = merge(lists, left, mid);
        //找到右边的merge
        ListNode l2 = merge(lists, mid+1, right);
        return mergeTwoLists(l1,l2);
    }


    //合并两个链表的
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

我觉得这个写法很牛，但当前阶段，我应该还写不出来。