C++ solution o(N) using recursion + stack to avoid modifying the lists


  • 1
    G
    class Solution {
    public:
    
        int GetLen(ListNode *l1)
        {
            return (l1 == NULL ? 0 : 1 + GetLen(l1->next));
        }
        
        //
        // Add assumes that l1 and l2 are of equal length
        // 
        ListNode *Add(ListNode *l1, ListNode *l2, int &C)
        {
            if(l1 == NULL)
            {
                return NULL;
            }
            
            ListNode *Res = NULL;
            
            ListNode *Temp = Add(l1->next,l2->next,C);
            Res = new ListNode(l1->val + l2->val + C);
            C = (Res->val / 10);
            Res->val %= 10;
            Res->next = Temp;
            return (Res);
        }
    
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
        {
            int Len1 = GetLen(l1);
            int Len2 = GetLen(l2);
            
            vector<ListNode*> Stack;
            
            ListNode *N1 = l1, *N2 = l2;
            
            while(Len1 > Len2)
            {
                Stack.push_back(N1);
                N1 = N1->next;
                Len1--;
            }
            
            while(Len2 > Len1)
            {
                Stack.push_back(N2);
                N2 = N2->next;
                Len2--;
            }
            
            int Carry = 0;    
            ListNode *R1 = Add(N1,N2,Carry);
            
            while(Stack.empty() == false)
            {
                ListNode *Top = Stack.back();
                Stack.pop_back();
                
                ListNode *Add = new ListNode(Carry + Top->val);
                
                Carry = (Add->val / 10);
                Add->val %= 10;
                Add->next = R1;
                R1 = Add;
            }
            
            if(Carry)
            {
                ListNode *Add = new ListNode(Carry);
                Add->next = R1;
                R1 = Add;
            }
            
            return (R1);
        }
    };

Log in to reply
 

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