algorithm - 合并K个排序的链表，为什么复杂度为O(N * K * K)，而不是O(N * K)

我有以下解决方案，但我从其他评论员那里听说它是O(N * K * K)，而不是O(N * K)，其中N是K列表的（最大）长度，K是列表的数量例如，给定列表[1, 2, 3]和[4, 5]，N是3，K是2。

/**
 * 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;
                }
            }

            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;
    }
}

我的推理是，do-while循环的主体将发生N次（因为当遍历最长列表时，do-while循环的停止条件得到满足），而do-while循环的主体将发生for次（K），产生listNodes.length。
为什么上面的解决方案是O(n * k)？

最佳答案

生成的列表最多有n个k项。将这些项中的每一项相加花费o（k）（内部循环执行k次迭代以检查每个列表的头部）。因此，总运行时间是o（n*k*k）。