首页 > itarticle > leetcode “23. merge k sorted lists”

leetcode “23. merge k sorted lists”

admin 11月 13, 2020 0

Intuition

Using a minHeap to maintain all the values, and poll out.
The previous solution may meet a MLE. Because the input lists may be a huge count.
Instead of saving all the values at once, we can only save the head nodes of all the lists. Because there’re sorted listnodes, so the next values can be get using .next function, and we can add it to the heap when poll it’s previous node.

solution

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length < 1) {
            return null;
        }
        Comparator<ListNode> comparator = new Comparator<ListNode>() {
            public int compare(ListNode n1, ListNode n2) {
                return n1.val - n2.val;
            }
        };
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(comparator);
        for (ListNode node: lists) {
            if (node != null) {
                minHeap.add(node);
            }
        }
        ListNode dummyNode = new ListNode(-1);
        ListNode cur = dummyNode;
        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            cur.next = node;
            if (node.next != null) {
                minHeap.add(node.next);
            }
            cur = cur.next;
        }
        return dummyNode.next;
    }
}