Tuesday, October 17, 2017

445. Add Two Numbers II

https://leetcode.com/problems/add-two-numbers-ii/description/
Solution 1. Read the value to 2 vectors.
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<int> v1, v2;
        ListNode* ln, * res = nullptr;
        ln = l1;
        while(ln) {
            v1.push_back(ln->val);
            ln = ln->next;
        }
        ln = l2;
        while(ln) {
            v2.push_back(ln->val);
            ln = ln->next;
        }
        int NI = v1.size(), NJ = v2.size(), c = 0;
        for(int i=NI-1, j=NJ-1; i>=0||j>=0|| c; i--, j--, c/=10) {
            if(i>=0) c+=v1[i];
            if(j>=0) c+=v2[j];
            ln = new ListNode(c%10);
            ln->next = res;
            res = ln;
        }
        return res;
    }
Or use a stack:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1;
        stack<int> s2;
        ListNode* l = l1, * res=nullptr;
        while(l){
            s1.push(l->val);
            l = l->next;
        }
        l = l2;
        while(l) {
            s2.push(l->val);
            l = l->next;
        }
        l = nullptr;
        int c = 0;
        while(!s1.empty() || !s2.empty() || c) {
            if(!s1.empty()) {
                c += s1.top();
                s1.pop();
            }
            if(!s2.empty()) {
                c += s2.top();
                s2.pop();
            }
            l = new ListNode(c%10);
            l->next = res;
            res = l;
            c /= 10;
        }
        return res;
    }

No comments:

Post a Comment