Gfrktyl

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.

The time complexity is O(listLength * 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(numberOfLists)), and there are listLength * numberOfLists iterations.

You can get to O(listLength * numberOfLists * log(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 it's value has changed. (or remove it if it got to a null)