What's wrong with this Priority Queue based solution?


  • 0
    A

    I think a priority queue based solution would be a fit for this problem. But since the elements in the Priority queue(pq) are objects, I had to pass in a comparator for the pq for it to be able to compare the ListNode objects. However I am getting illegalargumentexception at the following line where I declare the priority queue:

    PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.length, comparator);

    The weird thing is that the solution works like a charm on my machine. My guess is we are not allowed to import comparator or pq? Any help would be really appreciated!

    Here is the full solution:

    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
    		Comparator<ListNode> comparator = new ListNodeComparator();
    		PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.length,
    				comparator); // <<<<<<<<< illegalargumentexception HERE 
    
    		for (int i = 0; i < lists.length; i++) {
    			ListNode temp = lists[i];
    			while (temp != null) {
    				pq.add(temp);
    				temp = temp.next;
    			}
    		}
    		ListNode head = new ListNode(0);
    		ListNode temp = head; 
    		while (pq.size() > 0) {
    			temp.next = pq.poll();
    			temp = temp.next;
    		}
    
    		return head.next;
    	}
    
    	public class ListNodeComparator implements Comparator<ListNode> {
    
    		@Override
    		public int compare(ListNode o1, ListNode o2) {
    			if (o1.val > o2.val)
    				return 1;
    			else if (o1.val < o2.val)
    				return -1;
    			else
    				return 0;
    		}
    
    	}
    }

Log in to reply
 

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