Merging K Sorted Linked Lists

Question

Specifically, how can I improve the time complexity of my algorithm (currently it is O(listLength * numberOfLists))? It only beats 5% of accepted LeetCode solutions, which surprised me.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */
class Solution {
 private void advance(final ListNode[] listNodes, final int index) {
 listNodes[index] = listNodes[index].next;
 }
 public ListNode mergeKLists(final ListNode[] listNodes) {
 ListNode sortedListHead = null;
 ListNode sortedListNode = null;
 int associatedIndex;
 do { 
 int minValue = Integer.MAX_VALUE;
 associatedIndex = -1;
 for (int listIndex = 0; listIndex < listNodes.length; listIndex++) {
 final ListNode listNode = listNodes[listIndex];
 if (listNode != null && listNode.val < minValue) { 
 minValue = listNode.val;
 associatedIndex = listIndex;
 }
 }
 // An associated index of -1 indicates no more values left in any of the given lists
 if (associatedIndex != -1) {
 if (sortedListNode == null) {
 sortedListNode = new ListNode(minValue);
 sortedListHead = sortedListNode;
 }
 else {
 sortedListNode.next = new ListNode(minValue);
 sortedListNode = sortedListNode.next;
 }
 advance(listNodes, associatedIndex);
 }
 }
 while (associatedIndex != -1);
 return sortedListHead;
 }
}

Note that the Solution class in addition to ListNode is already provided, the only code that I wrote was inside mergeKLists.

• vnp: You correctly determined the complexity of your approach. No surprise that it fares low. Strive for O(listLength * log(numberOfLists)).

Answer 1

The time complexity is \$O(\text{listLength} * \text{numberOfLists}^2)\$ because the check of which node is the smallest? is looking at one element of each list every iteration (so each iteration's complexity is \$O(\text{numberOfLists})\$, and there are \$\text{listLength} * \text{numberOfLists}\$ iterations.

You can get to \$O(\text{listLength} * \text{numberOfLists} * \log(\text{numberOfLists}))\$ by using a sorted list of the ListNode elements that you are checking in each iteration, instead of the unsorted array listNodes. Let's call this list sortedNodes. You can avoid checking each element of sortedNodes every iteration because you know the first one is the smallest, and once you take this first value into the merged list and advance the node - do a binary search to decide where to move the first element after its value has changed. (Or remove it if it got to a null.)

Answer 2

A comment suggests that you can get \$\mathcal{O}(n\log{m})\$, where \$n\$ is the total number of elements in all lists and \$m\$ is the number of lists. How would you get \$\mathcal{O}(n\log{m})\$? The answer is to maintain a container of sorted lists. Two possible containers are a SortedSet (e.g. TreeSet) or a PriorityQueue (implemented with a heap). Both have \$\mathcal{O}(\log{m})\$ insertions and removals. You would perform \$\mathcal{O}(n)\$ insertions and removals (i.e. one for each element of the lists). \$\mathcal{O}(n\log{m})\$ overall.

Your current code is \$\mathcal{O}(n\cdot m)\$, so \$\mathcal{O}(n\log{m})\$ would be an improvement asymptotically.

Consider

 public ListNode mergeKLists(final ListNode[] listNodes) {
 PriorityQueue<ListNode> lists = new PriorityQueue<>(Arrays.asList(listNodes));
 // create a dummy head so as to have the same logic for the first node as the others
 ListNode head = new ListNode(0);
 ListNode current = head;
 for (ListNode node = lists.poll(); node != null; node = lists.poll()) {
 current.next = new ListNode(node.val);
 current = current.next;
 if (node.next != null) {
 lists.add(node.next);
 }
 }
 return head.next;
 }

The for loop will run \$n\$ times (once for each element in the lists). The poll and add operations will each take \$\mathcal{O}(\log{m})\$ time. So \$\mathcal{O}(n\log{m})\$ overall. The creation of the PriorityQueue will take \$\mathcal{O}(m\log{m})\$, so that's \$\mathcal{O}((n + m)\log{m})\$. If we assume that none of the lists are empty, then \$m <= n\$, so \$\mathcal{O}(n\log{m})\$.

We return head.next to avoid the problem of checking on each iteration if we are inserting the first element of the list. The head itself is not part of the list that we are creating, just a placeholder. Another alternative would be to create the first element outside the list.

This code assumes that none of the entries in listNodes are null. If they can be, you'd need additional checking for that case. It also assumes that ListNode is comparable by val. If not, you'd have to pass a Comparator to the PriorityQueue constructor to implement that behavior. The SortedSet version is similar, with the same limitations.

With a Comparator and capacity set, null checking, without a dummy head, and with current declared as part of the loop declaration (for better scoping, as current is not used outside the loop):

 public ListNode mergeKLists(final ListNode[] listNodes) {
 PriorityQueue<ListNode> lists = new PriorityQueue<>(listNodes.length,
 new Comparator<ListNode>() {
 int compare(ListNode a, ListNode b) {
 return Integer.compare(a.val, b.val);
 }
 });
 for (ListNode node : listNodes) {
 if (node != null) {
 lists.add(node);
 }
 }
 if (lists.isEmpty()) {
 return null;
 }
 ListNode head = new ListNode(lists.poll().val);
 for (ListNode node = lists.poll(), current = head; node != null; node = lists.poll()) {
 current.next = new ListNode(node.val);
 current = current.next;
 if (node.next != null) {
 lists.add(node.next);
 }
 } 
 return head;
 }

I think that the dummy head is actually easier, but you may find this form more readable.

I haven't tested this, so beware of syntax errors, etc.