package com.q0023;

import com.q0203_remove_linked_list_elements.ListNode;

import java.util.PriorityQueue;

/**
 * @author xjn
 * @since 2020-06-03
 * 23. 合并K个排序链表
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        if(lists.length == 1){
            return lists[0];
        }
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>((a, b)-> a.val - b.val);
        for(ListNode listNode : lists){
            if(listNode != null) {
                priorityQueue.add(listNode);
            }
        }
        while (!priorityQueue.isEmpty()){
            ListNode poll = priorityQueue.poll();
            cur.next = poll;
            cur = poll;
            if(poll.next != null) {
                priorityQueue.add(poll.next);
            }
        }
        return dummyHead.next;
    }
}