Memory Limit Exceed error


  • 0
    Y

    Below I list two version of codes, of which the first one results in a "Memory Limit Exceed" error while the second is accepted. However, the only difference between the two version is that I use some integer val1 to replace (iterator->val) in some expression. Can anyone tell me why this happens? Thanks!

    1st version (Memory Limit Exceed)

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) 
        {
            //define two iterators for l1 and l2
            ListNode *iteratorL1=l1;
            ListNode *iteratorL2=l2;
            int val1=iteratorL1->val;
            int val2=iteratorL2->val;
            //construct the first node in the NodeList
            ListNode *newList=new ListNode((val1+val2)%10);
            int flag=(iteratorL1->val+iteratorL2->val)/10;
            
            ListNode *iterator=newList;
            
            while ((iteratorL1->next || iteratorL2->next) || flag)
            {
                if(iteratorL1->next)
                {
                    iteratorL1=iteratorL1->next;
                    val1=iteratorL1->val;
                }
                else
                    val1=0;
                if(iteratorL2->next)
                {
                    iteratorL2=iteratorL2->next;
                    val2=iteratorL2->val;
                }
                else
                    val2=0;
                
                ListNode *newNode=new ListNode((val1+val2+flag)%10);
                flag=(iteratorL1->val+iteratorL2->val+flag)/10;
                iterator->next=newNode;
                iterator=iterator->next;
            }
            
            return newList;
            
        }
    };
    

    2nd version (correct one)

    class Solution {
    public:
        ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) 
        {
            //define two iterators for l1 and l2, and two integer to store value in each node
            ListNode *iteratorL1=l1;
            ListNode *iteratorL2=l2;
            int val1=iteratorL1->val;
            int val2=iteratorL2->val;
            
            //construct the first node in the result NodeList
            ListNode *newList=new ListNode((val1+val2)%10);
            int flag=(val1+val2)/10;
            //iterator for the result NodeList
            ListNode *iterator=newList;
            
            while ((iteratorL1->next || iteratorL2->next) || flag)
            {
                if(iteratorL1->next)
                {
                    iteratorL1=iteratorL1->next;
                    val1=iteratorL1->val;
                }
                else
                    val1=0;
                if(iteratorL2->next)
                {
                    iteratorL2=iteratorL2->next;
                    val2=iteratorL2->val;
                }
                else
                    val2=0;
                
                ListNode *newNode=new ListNode((val1+val2+flag)%10);
                flag=(val1+val2+flag)/10;
                iterator->next=newNode;
                iterator=iterator->next;
            }
            
            return newList;
            
        }
    };

  • 1
    R

    Problem in your first solution is this line of code

            flag=(iteratorL1->val+iteratorL2->val+flag)/10;
    

    Within the while loop.
    What if iteratorL1 or iteratorL2 is NULL, after what you did in those "if" statements.
    Change that one to

    flag=(val1+val2+flag)/10;

    Will work


  • 0
    Y

    Thank you @ryanzhao! Do you mean the input NodeList are already NULL? I exclude the situation that iteratorL1 is Null using the two "if"s in the while loop (if next=null, stop iteration). But you're right that the problem is from the flag expression. If the end of the two list adds to over 10, then flag is always set to 1, which results in a infinite loop.


  • 0
    R

    suppose input in l1={5}, l2={6}. In this case, you want flag = (0+0+1) /10= 0, not (5+6+1)/10=1.


  • 0
    Y

    I get your idea. However just to clarify I put the calculation of the first node outside the while loop. So inside the loop it's actually calculating the second and following node, which, as you said, should make flag=0


Log in to reply
 

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