My Java Solution with a PriorityQueue and Comparator - with comments

  • 1
    public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // edge case - empty list
        ListNode nodes = null;
        if(lists.length == 0){
            return nodes;
        // edge case - single entry in list
            return lists[0];
        //merge k-sorted linked lists - use priority queue
        Comparator<ListNode> lnvc = new ListNodeValueComparator();
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(lists.length, lnvc);
        for(ListNode listNode: lists){
            //add a list node to a priority queue.
            if(listNode !=null){
                priorityQueue.offer(listNode); //adds to the priority queue
        ListNode head = null;
            //poll() element from Queue
            ListNode smallestNow = priorityQueue.poll();
            if(!=null){ // if linked list is not empty, offer next node to the heap
       = null;
            //get smallest node from list
            if(nodes == null){
                nodes = smallestNow;
                //head becomes the first smallest element
                head = smallestNow; 
            } else {
       = smallestNow;
                nodes =;
        return head;
    //declare a custom comparator
    private class ListNodeValueComparator implements Comparator<ListNode>{
         * Compare ListNode
         public int compare(ListNode listNode1, ListNode listNode2){
            //compares integer values of both nodes 
            return, listNode2.val);   


  • 0

    May I ask why we need to override the comparator in priorityqueue here? Because priorityqueue will pop out the least element by default.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.