23.合并 K 个升序链表

发布时间:2024年01月15日

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 = [[]]
输出:[]

提示:

  • 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

思路:

首先:该题使用java的PriorityQueue数据结构(PriorityQueue实质就是小根堆),你add()一个数,PriorityQueue会自动排序,poll()一个数,会返回堆中的最小值。

大体流程:

  • 遍历lists每个元素(每个元素就是一个链表),将每个链表的头结点加入到小根堆中,然后首次poll()出来的就是lists所有链表中头最小的,拿它当做新链表的头。
  • 然后判断该链表还有没有后继结点,如果有再加入到小根堆
  • 再poll()出来一个,拼到新链表的后面,如果poll()的节点还有后继节点再加入,什么时候小根堆为空了

返回新链表

public class Problem_0023_MergeKSortedLists {

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a ,b) -> a.val - b.val);
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                heap.add(lists[i]);
            }
        }
        if (heap.isEmpty()) {
            return null;
        }
        ListNode head = heap.poll();
        // pre负责拼接新链表
        ListNode pre = head;
        if (pre.next != null) {
            heap.add(pre.next);
        }
        while (!heap.isEmpty()) {
            ListNode cur = heap.poll();
            pre.next = cur;
            pre = cur;
            if (cur.next != null) {
                heap.add(cur.next);
            }
        }
        return head;
    }
}
文章来源:https://blog.csdn.net/weixin_49435563/article/details/135577973
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。