# I can't understand why the time limit exceeds ππ

• ``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
if(l1==NULL) return l2;
if(l2==NULL) return l1;
while(l1&&l2){
if(l1->val<=l2->val) {q->next=l1;q=q->next;l1=l1->next;}//q=q->next别忘了
else{q->next=l2;q=q->next;l2=l2->next;}
}
if(l1==NULL) q->next=l2;
if(l2==NULL) q->next=l1;

}
ListNode *mergeKLists(vector<ListNode *> &lists) {
if (lists.size()==0) return NULL;
if(lists.size()==1) return lists[0];

int i;
for(i=1;i<lists.size();i++){
}
}

};``````

• You algorithm is O(k^2 n) complexity in time. The computation of merging two sorted lists is proportional to the size of the longest list. Suppose the input k lists are of the same length n,
the complexity would be n + 2n + 3n ... (k-1)n ~ O(k^2 n). If k is large number, your algorithm is not acceptable.

• O(nlgn)

mergeKLists = mergeTwo( mergeKLists(left half), mergeKLists(right half))

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.