A simple solution using priority queue O(kn logn) time complexity


  • 0
    S

    Any comments are welcome :). It would be amazing if someone can suggest an approach that does not use a heap.

    public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            
            Queue<Integer> minHeap = new PriorityQueue<Integer>();
    
            for(int i = 0; i < lists.length; i++){
                
                ListNode head = lists[i];
                ListNode temp = head;
                while(temp != null){
                    minHeap.add(temp.val);
                    temp = temp.next;
                }
            }
            ListNode result = new ListNode(0);
            ListNode temp = result;        
            while(minHeap.peek() != null){
                temp.next = new ListNode(minHeap.poll());
                temp = temp.next;
            }
            return result.next;
        }
    }
    

Log in to reply
 

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