/**
 * 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) {

        /* new ListNode to store sum,
            the first element is a dummy node which we will discard */
        ListNode* sum = new ListNode(-1);

        // pointers to traverse the 3 lists
        ListNode* p1 = l1;
        ListNode* p2 = l2;
        ListNode* p3 = sum;

        // carry over to next digit
        int carry = 0;

        /* loop until both summands no longer have digits remaining
            and there is no carry remaining */
        while (p1 != NULL || p2 != NULL || carry > 0){

            // add up the two digits and the carry digit
            int curr = carry;
            carry = 0;

            if (p1 != NULL){
                curr += p1->val;
                p1 = p1->next;
            }
            if (p2 != NULL){
                curr += p2->val;
                p2 = p2->next;
            }

            // check for carry
            if (curr > 9){
                curr -= 10;
                carry = 1;
            }

            // set next node to computed digit
            ListNode* temp = new ListNode(curr);
            p3->next = temp;
            p3 = p3->next;
        }

        // return discarding the first -1 dummy node
        return sum->next;
    }
};