/**
1. 先将所有链表头加入优先队列, 每次取出堆顶后, 把它的下一个节点再加进去
2. 设总节点数为n, 时间复杂度为 nlogk
*/

/**
1. 二分合并, 将链表两两合并, 每次可减少一半的链表数量, 直到合并成一个链表
2. 设总节点数为n, 时间复杂度为 nlogk
*/


//吐槽下,这个题应该是medium 难度

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // return minHeap(lists);
        return divide(lists);
    }   

    public ListNode divide(ListNode[] lists){
        if (lists == null || lists.length == 0 ) return null;
        int n = lists.length ;
        int i = 0, j = n-1;
        while (n != 1){
            while(i < j){
                lists[i] = merge(lists[i], lists[j]);
                i++;
                j--;
            }
            n = (n+1)>>1;
            i = 0;
            j = n-1;
        }
        return lists[0];
    }

    private ListNode merge(ListNode a, ListNode b){
        if (a == b) return a;
        if (a == null || b == null) return a== null? b:a;
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while (a != null && b != null){
            if (a.val < b.val){
                p.next = a;
                a = a.next;
            } else {
                p.next = b;
                b = b.next;
            }
            p = p.next;
        }
        if (a != null) p.next = a;
        if (b != null) p.next = b;
        return dummy.next;
    }


    public ListNode minHeap(ListNode lists[]){
        Queue<ListNode> queue = new PriorityQueue<>((a,b)->(a.val - b.val));
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        for (int i = 0 ; i < lists.length; i++){
            if (lists[i] != null) queue.offer(lists[i]);
        }
        while (!queue.isEmpty()){
            ListNode node = queue.poll();
            p.next = node;
            p = p.next;
            if (node.next != null) queue.offer(node.next);
        }
        return dummy.next;
    }

}