Leetcode 445 Solution

This article provides solution to leetcode question 445 (add-two-numbers-ii)

https://leetcode.com/problems/add-two-numbers-ii

Solution

/**
 * 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) {
        vector<int> v1;
        vector<int> v2;

        v1.reserve(1000);
        v2.reserve(1000);

        while (l1)
        {
            v1.push_back(l1->val);
            l1 = l1->next;
        }

        while (l2)
        {
            v2.push_back(l2->val);
            l2 = l2->next;
        }

        int carry = 0;
        ListNode* p = NULL;

        while (v1.empty() == false || v2.empty() == false)
        {
            int val1 = 0;
            int val2 = 0;

            if (v1.empty() == false)
            {
                val1 = v1.back();
                v1.pop_back();
            }

            if (v2.empty() == false)
            {
                val2 = v2.back();
                v2.pop_back();
            }

            int val = val1 + val2 + carry;

            if (val >= 10)
                val -= 10, carry = 1;
            else
                carry = 0;

            if (p == NULL)
                p = new ListNode(val);
            else
            {
                ListNode* q = new ListNode(val);
                q->next = p;
                p = q;
            }
        }

        if (carry)
        {
            ListNode* q = new ListNode(1);
            q->next = p;
            p = q;
        }

        return p;
    }
};