Merge k Sorted Lists

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

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
  public ListNode mergeKLists(ArrayList<ListNode> lists) {
              if(lists.size() == 0) return null;


        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.size(), new Comparator<ListNode>(

        ) {
            @Override
            public int compare(ListNode listNode, ListNode listNode2) {

                if(listNode.val < listNode2.val) return -1;
                else if(listNode.val > listNode2.val) return 1;
                else return 0;
            }
        });

        for(ListNode temp: lists){
            if(temp != null)
                pq.add(temp);
        }

        ListNode head = new ListNode(-1);
        ListNode prev = head;

        while(!pq.isEmpty()){

            ListNode temp = pq.poll();
            prev.next = temp;

            if(temp.next != null)
                pq.add(temp.next);

            prev = prev.next;
        }

        return head.next;
    }

}