C++ recursive


  • 0
    F

    solve it recursively:

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
        int add(stack<int>& a, stack<int>& b, ListNode* froma){
            if(froma == nullptr){return 0;}
            int ret = add(a, b, froma->next);
            int tmpa = a.top();
            a.pop();
            int tmpb = 0;
            if(!b.empty()){
                tmpb = b.top();
                b.pop();
            }
            int sum = tmpa + tmpb + ret;
            froma->val = sum % 10;
            return sum / 10;
        }
        
        int addN(int lena, int lenb, ListNode* froma, ListNode* fromb){
            if(froma == nullptr){return 0;}
            int tmpa = froma->val;
            int tmpb = 0;
            int ret = 0;
            if(lena > lenb){
                ret = addN(lena - 1, lenb, froma->next, fromb);
            }else{
                ret = addN(lena - 1, lenb - 1, froma->next, fromb->next);
                tmpb = fromb->val;
            }
            int sum = tmpa + tmpb + ret;
            froma->val = sum % 10;
            return sum / 10;
        }
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            // stack<int> a;
            // stack<int> b;
            assert(l1);
            assert(l2);
            int lena = 0;
            int lenb = 0;
            ListNode* ptr = l1;
            while(ptr){
                // a.push(ptr->val);
                lena++;
                ptr = ptr->next;
            }
            ptr = l2;
            while(ptr){
                // b.push(ptr->val);
                lenb++;
                ptr = ptr->next;
            }
            // if(a.size() < b.size()){swap(l1, l2); swap(a, b);}
            if(lena < lenb){swap(l1, l2);swap(lena, lenb);}
            ListNode* h = new ListNode(0);
            h->next = l1;
            // auto ret = add(a, b, h->next);
            auto ret = addN(lena, lenb, l1, l2);
            if(ret){h->val = ret;return h;}
            return h->next;
        }
    };
    

Log in to reply
 

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