力扣023 合并k个排序列表-摩杜云开发者社区

力扣023 合并k个排序列表

题目:

给你一个链表数组，每个链表按升序排序。k``lists

将所有链接列表合并为一个排序的链接列表并返回它。

示例 1：

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

示例 2：

Input: lists = []
Output: []

示例3：

Input: lists = [[]]
Output: []

约束：

k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i]按升序排序。
的总和不会超过。lists[i].length``104

解题思路：

首先我们想到要将k个有序链表合并成为一个有序链表，肯定会涉及到链表节点之间的比较。所以我们首先定义一个比较器用来比较链表节点之间的大小其次我们用到一个优先队列第一次先将每个链表的头节点放入优先队列中然后每次从这个优先队列中取出一个元素就判断这个节点的后面是否还存在节点如果存在节点就将它的下一个节点又放入到优先队列中，始终秉持“取出一个元素加入一个元素”，直到这个优先队列为空。并依次将取出的元素串联起来形成一个新的链表最后返回这个新链表的头部。

代码:

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 给一个链表数组，每个链表都是升序有序排列，请你将所有链表合并到一个有序的升序的链表中并返回合并后的链表
 */
public class MergeAscLists {
    //1.首先定义一个节点类
    public static class ListNode{
        public int value;
        public ListNode next;

        public ListNode(int value) {
            this.value = value;
        }
    }

    //2.再自己定义一个比较器
    public static class ListNodeComparator implements Comparator<ListNode>{
        /**
         * 重写比较的方法：
         * 所有的比较方法如果返回的是负数那么第一个参数o1在前面第二个参数o2在后面
         * 如果返回的是正数那么第二个参数o2在前面第一个参数o1的后面
         * 如果返回的是0那么第一个参数和第二个参数相等
         * @param o1
         * @param o2
         * @return
         */
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.value - o2.value;
        }
    }

    //3.合并多个有序链表,参数为一个节点数组每个节点表示一个链表的头节点代表一个链表
    public static ListNode mergeLists(ListNode[] lists){
        //3.1如果数组为空返回null
        if (lists == null) {
            return null;
        }
        //3.2定义一个优先队列(其实这个优先队列是一个小根堆)
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
        //3.3首先我们先将每个链表的头节点放进这个优先队列heap
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null){
                heap.add(lists[i]);
            }
        }
        //3.3.1如果这个优先队列heap为空则返回null
        if(heap.isEmpty()){
            return null;
        }
        //3.3.2定义一个变量为head,head指向优先队列取出的元素 也就是先弹出一个作为整体的头部 先抓住最后返回
        ListNode head = heap.poll();
        //3.3.3定义一个变量pre指向head
        ListNode pre = head;
        /*
        4.判断pre后面还有没有节点(因为刚开始lists数组中每个元素代表的是每个链表的头节点
        所以这个操作就是判断链表后面还有没有节点如果有就将它加入到优先队列中)
         */
        if (pre.next != null){
            heap.add(pre.next);
        }
        //5.依次从这个优先队列heap中取出元素,每弹出一个就挂在head的next指针上
        while (!heap.isEmpty()){
            //5.1弹出一个元素
            ListNode cur = heap.poll();
            //5.2将弹出的这个元素挂在head的next指针上因为pre指向head
            pre.next = cur;
            //5.3然后pre继续往下走 指向现在的cur
            pre = cur;
            //5.4如果当前的cur的next指针不为空就将它加入到优先队列heap中
            if(cur.next != null){
                heap.add(cur.next);
            }
        }
        /*
        总结:也就是出来一个进去一个出来一个进去一个直到这个优先队列为空的时候
         */
        //6.最后返回第一次抓住的head这就是合并后的链表的头节点
        return head;
    }
}