大家好！我是曾续缘🤎
今天是《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;
    }
}

查看代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    h := hp{}
    for _, head := range lists {
        if head != nil {
            h = append(h, head)
        }
    }
    heap.Init(&h)

    dummy := &ListNode{}
    cur := dummy
    for len(h) > 0 {
        mn := heap.Pop(&h).(*ListNode)
        if mn.Next != nil {
            heap.Push(&h, mn.Next)
        }
        cur.Next = mn
        cur = cur.Next
    }
    return dummy.Next
}

type hp []*ListNode
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(*ListNode)) }
func (h *hp) Pop() any { a:= *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

解题方法 ​

Code ​

解题方法

Code