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


  • 0
    L
    /**
     * Definition for singly-linked list.
     * 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;
            ListNode *head,*q,*temp;
            if(l1->val<=l2->val) {head=l1;l1=l1->next;}
            else {head=l2;l2=l2->next;}
            q=head;
            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;
            return head;
            
        }
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            if (lists.size()==0) return NULL;
            if(lists.size()==1) return lists[0];
            ListNode *head;
            head=lists[0];
            
            int i;
      //      head=mergeTwoLists(lists[0],lists[1]);
            for(i=1;i<lists.size();i++){
                head=mergeTwoLists(head,lists[i]);
            }
            return head;
        }
        
    };

  • 0
    G

    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.


  • 0
    B

    O(nlgn)

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


Log in to reply
 

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