Tukukkk

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.