23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

• using heap to traverse all nodes in lists

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>(10, new Comparator<ListNode>(){
           @Override
           public int compare(ListNode n1, ListNode n2){
               return n1.val -n2.val;
           }
        });
        for(ListNode node : lists){
            if(node != null)
                heap.offer(node);
        }
        ListNode head = null;
        ListNode tail = null;
        while(heap.size() > 0){
            ListNode node = heap.poll();
            if(head == null){
                head = tail = node;
            }else{
                tail.next = node;
                tail = tail.next;
            }
            if(node.next != null){
                heap.offer(node.next);
            }
        }

        return head;
    }
}

• similiar to merge 2 sorted list, using merge sort.