package problems;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import structures.ListNode;
public class MergeKSortedList {
@SuppressWarnings("null")
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null && lists.length == 0) {
return null;
}
Queue<ListNode> q = new PriorityQueue<ListNode>(20,
new Comparator<ListNode>() {
public int compare(ListNode l1, ListNode l2) {
if (l1.val < l2.val)
return 1;
else if (l1.val > l2.val)
return 1;
else
return 0;
}
});
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
q.add(lists[i]);
}
}
ListNode dummy = new ListNode(0);
ListNode root = dummy;
while (!q.isEmpty()) {
dummy.next = q.poll();
dummy = dummy.next;
if (dummy.next != null) {
q.add(dummy.next);
}
dummy.next = null;
}
return root.next;
}
}
Java log(nlogk) Using Heap (priority queue)


Unfortunately, the complexity of the proposed heapbased algorithm is still O(nklog(k)).

As you can see, in the while loop, the step of adding an element to the priority queue is "q.add(dummy.next)". This step requires O(log(k)) time complexity, which is the time required in heap adjustment.

We can expect that the while loop will run O(n*k) times to put all nodes from k lists into the final sorted list.

Based on the observations from 1 and 2, we can easily conclude that the actual time complexity is O(nklog(k)) for the algorithm.


I don't agree with your analysis. Below is my analysis Assuming priority queue built using Heap 1. Complexity of initial heap of size k = O(k). 2. HEAPIFY takes O(logk) 3. (nk) times it needs to be Heapfy. So complexity would be =>O(k) + O((nk)*logk) =>O(k) + O(nlogk)o(klogk) => O(nlogk).