Why does my solution always encounter "memory limit exceeded" error


  • 0
    U

    class Solution {
    public:

    ListNode * mergeTwo(ListNode * a, ListNode *b){
        ListNode * org = new ListNode(0);
    	ListNode * cur =org;
        
        while(a && b){
            if(a->val<b->val){
                cur->next = a;
                a = a->next;
            }
            else{
                cur->next = b;
                b= b->next;
            }
            cur = cur->next;
        }
        
        
        if(b){
            cur->next = b;
        }
        else
            cur->next =a;
        
        ListNode * p = org->next;
        delete org;
        return p;
    }
    
    
    ListNode * aux(vector<ListNode *> a, int l, int r){
        if(a.empty() || l>r) return nullptr;
        if(l==r) return a[l];
        
        int m = (l+r)/2;
        return mergeTwo(aux(a, l , m),aux(a, m+1,r));
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ret = nullptr;
        
        if(lists.size()==0) return ret;
        if(lists.size()==1) return lists[0];
        
        return aux(lists, 0, lists.size()-1);
    
    }
    

    };


  • 0
    J

    Your code bugs me for a while. Your algorithm is correct and perfect. However, your problem is your parameter list of

    ListNode* aux(vector<ListNode * > a, int l, int r)
    

    function. The vector< ListNode > a* should
    be "vector< ListNode > & a*". In this case, the big list will be passed by reference but not by COPY. If you copy the whole list every time in your recursive call, you will run out of memory.

    Actually, for further discuss, this is the problem of C++. In java every object type is passed by reference by default and it's more reasonable than C++ in terms of programming language design.

    Good luck!


Log in to reply
 

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