Simple Java Solution using Priority Queue


  • 0
    S
    /**
     * 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) {
            if(lists == null || lists.length == 0) {
                return null;
            }
            PriorityQueue<ListNode> minHeap = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
                @Override
                public int compare(ListNode n1, ListNode n2){
                    return Integer.compare(n1.val, n2.val);
                }
            });
            
            for(ListNode curNode : lists) {
                if(curNode != null) {
                    minHeap.add(curNode);
                }
            }
            
            ListNode result = null;
            ListNode prev = null;
            
            while(!minHeap.isEmpty()) {
                ListNode curMin = minHeap.poll();
                if(curMin.next != null) {
                    minHeap.add(curMin.next);
                    curMin.next = null;
                }
                if(result == null) {
                    result = curMin;
                } else {
                    prev.next = curMin;
                }
                prev = curMin;
            }
            
            return result;
        }
    }

Log in to reply
 

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