> LeetCode:合并K个升序链表_23 - Yuyy
Yuyy
Yuyy
LeetCode:合并K个升序链表_23

思路

这题是21的升级版,从两路归并到多路归并,其中运用了优先队列来优化。感觉这题谈不上困难,只是运用了两个知识点,逻辑不复杂。

题目

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

 

示例 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
Related Topics
  • 链表
  • 分治
  • 堆(优先队列)
  • 归并排序
  • 👍 1492
  • 👎 0
  • 代码

            public ListNode mergeKLists(ListNode[] lists) {
                // 边界问题得注意
                if (lists.length == 0) {
                    return null;
                }
                // 虚拟头节点
                ListNode dummy = new ListNode();
                ListNode p = dummy;
                ListNode temp;
                // 利用优先队列优化,不然每次都需要对所有头结点遍历,优先队列的好处就是可以动态的调整内部顺序
                final Queue<ListNode> listNodes = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
                for (ListNode listNode : lists) {
                    // 边界问题得注意
                    if (listNode == null) {
                        continue;
                    }
                    listNodes.offer(listNode);
                }
    
                // 多路归并
                while ((temp = listNodes.poll()) != null) {
                    p.next = temp;
                    p = p.next;
                    if (temp.next != null) {
                        listNodes.offer(temp.next);
                    }
                }
    
                return dummy.next;
            }
    

    发表评论

    textsms
    account_circle
    email

    Yuyy

    LeetCode:合并K个升序链表_23
    思路 这题是21的升级版,从两路归并到多路归并,其中运用了优先队列来优化。感觉这题谈不上困难,只是运用了两个知识点,逻辑不复杂。 题目 给你一个链表数组,每个链表都已经按升序排…
    扫描二维码继续阅读
    2021-09-06
    友情链接
    标签
    归档
    近期文章