[数据结构与算法]java合并k个有序链表

1.3 合并k个有序链表

• 题目来源：leetcode 23题 （https://leetcode.cn/problems/merge-k-sorted-lists/）

• 题设：

  

• 解答

将链表数组中的每个链表加入到优先级队列当中，然后通过优先级队列进行比较

lists = [[1,4,5], [1,3,4], [2,6]]

我们在加入优先级队列的时候，我们可以暂时看做结点和后继结点断开

这样的话

第一轮的优先级队列：1 1 2

经过比较器poll出1，然后1的后继，即4加入到优先级队列，此时优先级队列为： 1 2 4

按照这个思路，整体的顺序应该是：

1 1 2 poll 1 add 4

1 2 4 poll 1 add 3

2 3 4 poll 2 add 6

3 4 6 poll 3 add 4

4 4 6 poll 4 add 5

4 5 6 poll 4 4的后继为空（第二个链表）所以不add

5 6 poll 5 5的后继为空（第一个链表）所以不add

6 poll 6

所以我们得到的最终结果为 1 1 2 3 4 4 5 6

    /*
     * 合并k个有序链表
     * @author xiaozhu
     * @date 2022/7/18 22:19
     * @param lists
     * @return Learn_List.ListNode
     */
    public ListNode mergeKLists(ListNode[] lists) {

        if (lists.length == 0) {
            return null;
        }

        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;

        //使用优先级队列
        //有两个参数，lists,length为优先级队列的大小，(a, b) -> (a.val - b.val)为比较器，使得每次poll出来的结点为最小
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> (a.val - b.val));

        //遍历题设中的链表数组，将链表加入到优先级队列中
        for (ListNode head : lists) {
            if (Optional.ofNullable(head).isPresent()) {
                pq.add(head);
            }
        }

        while (!pq.isEmpty()) {

            //此时poll出来的为最小结点
            ListNode node = pq.poll();
            p.next = node;

            if (Optional.ofNullable(node.next).isPresent()) {
                pq.add(node.next);
            }

            p = p.next;

        }

        return dummy.next;

    }


    public ListNode mergeKLists2(ListNode[] lists) {

        if (lists.length == 0) {
            return null;
        }

        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;

        //使用优先级队列
        //有两个参数，lists,length为优先级队列的大小，(a, b) -> (a.val - b.val)为比较器，使得每次poll出来的结点为最小
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> (a.val - b.val));

        //遍历题设中的链表数组，将链表加入到优先级队列中
        for (ListNode head : lists) {
            if (head != null) {
                pq.add(head);
            }
        }

        while (!pq.isEmpty()) {

            //此时poll出来的为最小结点
            ListNode node = pq.poll();
            //填入到新的链表中
            p.next = node;

            if (node.next != null) {
                pq.add(node.next);
            }

            p = p.next;

        }

        return dummy.next;

    }

关于优先级队列的使用，读者可以看我的另一篇文章

(39条消息) java中优先级队列的基本使用_xiaozhuxuejava的博客-CSDN博客_java优先队列使用

如有冒犯和错误，欢迎指正