TLE by using java PriorityQueue

  • 0

    the code is here:

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) return null;
        Queue<ListNode> queue = new PriorityQueue<>(lists.length,new Comparator<ListNode>(){
    		public int compare(ListNode l1, ListNode l2) {
    			return l1.val - l2.val;
        ListNode head = new ListNode(0);
        ListNode p = head;
        for(ListNode node : lists) {
            if(node != null)
        while(!queue.isEmpty()) {
        	ListNode node = queue.poll(); = node;
        	if( != null)
        	p =;

    The result is TLE, but if I change the "compare" method like this:

    public int compare(ListNode l1, ListNode l2) {
          if (l1.val < l2.val)
                return -1;
          else if (l1.val == l2.val)
                return 0;
                return 1;

    the result is AC, can anybody tell me why?

  • 0

    Because your original comparator is wrong. It will overflow. Imagine that you compare Integer.MAX_VALUE with -1 with your comparator. It will give a negative value.

Log in to reply

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