C++ solution using stack


  • 0
    M

    The basic idea is use stack to store reversed digit and then add the summation results of corresponding digits in the reverse order.

    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            stack<int> s1, s2;
            while(l1) {
                s1.push(l1->val);
                l1 = l1->next;
            }
            while(l2) {
                s2.push(l2->val);
                l2 = l2->next;
            }
            int carry = 0;
            ListNode dummy(0);
            while(!s1.empty() || !s2.empty() || carry) {
                if(!s1.empty()) {
                    carry += s1.top();
                    s1.pop();
                }
                if(!s2.empty()) {
                    carry += s2.top();
                    s2.pop();
                }
                ListNode* newNode = new ListNode(carry%10);
                newNode->next = dummy.next;
                dummy.next = newNode;
                carry /= 10;
            }
            return dummy.next;
        }
    };
    

Log in to reply
 

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