class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(-1), d = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
        for(ListNode head : lists){
            if(head != null) pq.offer(head);
        }

        while(!pq.isEmpty()){
            ListNode cur = pq.poll();
            d.next = cur;
            d = d.next;
            if(cur.next != null) pq.offer(cur.next);
        }

        return dummy.next;
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    ListNode merge(ListNode[] lists, int l, int r){
        if(l > r) return null;
        if(l == r) return lists[l];

        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode mergeTwoLists(ListNode list1, ListNode list2){
        ListNode l1 = list1, l2 = list2;
        ListNode dummy = new ListNode(-1), d = dummy;

        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                d.next = l1;
                l1 = l1.next;
            }else{
                d.next = l2;
                l2 = l2.next;
            }
            d = d.next;
        }
        d.next = l1 == null ? l2 : l1;

        return dummy.next;
    }
}