这段代码（来自leetcode）的时间复杂度是多少？

Question

bool cmp(ListNode *a, ListNode *b) {
return a->val < b->val;
}
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
    ListNode *dummy = new ListNode(-1);
    ListNode *curr = dummy;

    //init
    vector<ListNode*> currNodes;
    for(int i = 0; i < lists.size(); ++i){
        if(lists[i] != NULL){
            currNodes.push_back(lists[i]);
        }
    }

    while(!currNodes.empty()){
        sort(currNodes.begin(), currNodes.end(), cmp);
        curr->next = currNodes[0];
        curr = curr->next;

        if(currNodes[0]->next != NULL){
            currNodes.push_back(currNodes[0]->next);
        }
        currNodes.erase(currNodes.begin());
    }

    return dummy->next;
}
};

由于std：：sort的时间复杂度为nlog(n)，我们有(N1+N2....Nk)次迭代，因此我假设总的时间复杂度为O((N1+N2....+Nk)klog(k))。但是在每次迭代中，vectorcurrnodes的大小可能会有所不同，所以我有点困惑。有人能证实这一点吗？

2.我还在leetcode论坛上看到了另一个使用“合并排序”思想的解决方案。它每次都合并两个链表。

public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    if(lists.isEmpty()) return null;
    if(lists.size() == 1) return lists.get(0);
    int k = lists.size();
    int log = (int)(Math.log(k)/Math.log(2));
    log = log < Math.log(k)/Math.log(2)? log+1:log; // take ceiling
    for(int i = 1; i <= log; i++){
        for(int j = 0; j < lists.size(); j=j+(int)Math.pow(2,i)){
            int offset = j+(int)Math.pow(2,i-1);
            lists.set(j, mergeTwoLists(lists.get(j), (offset >= lists.size()? null : lists.get(offset))));
        }
    }
    return lists.get(0);
}


public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    if(l1 == null) return l2;
    if(l2 == null) return l1;
    ListNode head = l1.val > l2.val? l2:l1;
    if(head.equals(l2)){
        l2 = l1;
        l1 = head;
    }
    while(l1.next != null && l2 != null){
        if(l1.next.val > l2.val){
            ListNode tmp = l1.next;
            l1.next = l2;
            l2 = l2.next;
            l1 = l1.next;
            l1.next = tmp;
        }
        else
            l1 = l1.next;
    }
    if(l2 != null){
        l1.next = l2;
    }
    return head;
}
}

我想知道这个解决方案的时间复杂度是多少？因为它每次合并两个链表，所以有log(n)迭代。但是每次迭代后链表会变长（因为它是从两个链表合并而来的），如何计算每次迭代的时间复杂度，然后将它们相加？

提前谢谢：）

Answer 1

以下是我的解决方案。复杂度是（从k个列表中找出1分钟）*(n个节点）我会说它是O(kn)，其中k是列表的数量，最佳解决方案是O(nlogk)参见这里：如何用合并排序对k个排序的数组进行排序

但这对leetcode来说已经足够了，所以我没有做最小堆

//http://oj.leetcode.com/problems/merge-k-sorted-lists/

public ListNode mergeKLists(ArrayList<ListNode> lists) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    ListNode cursor = new ListNode(Integer.MAX_VALUE);
    ListNode head = cursor;
    int min = Integer.MAX_VALUE;
    int index = -1;
    while(lists.size()>0){
        for(int i=0; i<lists.size(); i++){//get 1 min
            if(lists.get(i)!=null && lists.get(i).val<min){
                min = lists.get(i).val;
                index = i;
            }
            if(lists.get(i)==null){
                lists.remove(i);
                i--;
            }
        }
        if(index>=0){//put the min in
            cursor.next = lists.get(index);
            cursor = cursor.next;
            lists.set(index,lists.get(index).next);
            if(lists.get(index)==null){
                lists.remove(index);
            }
            min = Integer.MAX_VALUE;
        }
    }
    return head.next;
}