Java Solution with PriorityQueue


  • 0
    A

    Use a min-heap (priority queue) to store the head (minimum) of each list. Remove the minimum element from the heap and add the next element from the corresponding list to the heap.

    public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null | lists.length == 0) {
                return null;
            }
            PriorityQueue<ListNode> q = new PriorityQueue<>(lists.length, 
                new Comparator<ListNode>() {
                    public int compare(ListNode a, ListNode b) {
                        return Integer.compare(a.val, b.val);
                    }
                });
            for (ListNode list : lists) {
                if (list != null) {
                    q.add(list);
                }
            }            
                
            ListNode dummy = new ListNode(0);
            ListNode n = dummy;
            while (!q.isEmpty()) {
                ListNode tmp = q.poll();
                n.next = tmp;
                
                if (tmp.next != null) {
                    q.offer(tmp.next);
                }
                
                n = n.next;
            }
            return dummy.next;
        }
    }

Log in to reply
 

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