LeetCode link

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
    }
}