大家好！我是曾续缘🤎
今天是《LeetCode 热题 100》系列
发车第 34 天
链表第 13 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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
难度：💝💝💝

解题方法

对于合并两个有序链表，我们可以使用两个指针分别指向两个链表的头节点，然后通过比较节点的值大小来决定选择哪一个节点，将其连接到合并后的链表中，然后移动指针继续比较。

而当我们合并K个有序链表时，如果使用K个指针来判断选择哪个节点，每次判断都需要遍历K个指针，效率较低。

为了优化时间复杂度，我们可以使用小根堆来帮助我们快速找到当前K个链表中值最小的节点，可以保证在 $O (l o g K)$ 时间内找到最小值。

首先自定义比较器，用于告诉PriorityQueue如何比较ListNode。在这里，我们根据ListNode的值来进行比较，以便在PriorityQueue中实现按值的升序排列。
我们创建一个虚拟的头节点(dummy)和一个指向尾部的节点(tail)。然后开始循环，每次从PriorityQueue中取出当前最小的节点，将其接到tail的后面，然后更新tail指针。如果取出的节点仍有下一个节点，我们将其下一个节点加入PriorityQueue中。
循环直到小根堆为空，返回dummy.next，即合并后的链表头节点。

Code

查看代码

java

/**
 * 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 {
    class ListNodeComparator implements Comparator<ListNode>{
        public int compare(ListNode l1, ListNode l2) {
            return l1.val - l2.val;
        }
    }
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> q = new  PriorityQueue<>(new ListNodeComparator());
        for(ListNode node : lists){
            if(node != null){
                q.offer(node);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while(!q.isEmpty()){
            ListNode cur = q.poll();
            tail.next = cur;
            tail = tail.next;
            if(cur.next != null){
                q.offer(cur.next);
            }
        }
        return dummy.next;
    }
}

解题方法 ​

Code ​

解题方法

Code