/**
 * 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) {
        ListNode* res = NULL;

        if (size(l1) < size(l2))
            res = add(l1, l2);
        else
            res = add(l2, l1);

        return res;
    }

private:

    /**
     * Input: A list
     * Output: size of the list
     */
    static int size(const ListNode *l) {
        int size = 0;
        while(l != NULL)
            ++size, l = l->next;
        return size;
    }

    /**
     * Input: Two lists l1 and l2 with size(l1) <= size(l2)
     * Output: result list
     */
    ListNode* add(const ListNode *l1, const ListNode *l2) {
        ListNode *head, *l;
        register bool carry_over = false;
        int x = l1->val + l2->val + carry_over;

        if (x > 9) {
            carry_over = true;
             x -= 10;
        }
        head = l = new ListNode(x);
        l1 = l1->next;
        l2 = l2->next;

        while (l1 != NULL) {
            x = l1->val + l2->val + carry_over;
            if (x > 9) {
                carry_over = true;
                x -= 10;
            } else
                carry_over = false;
            l = l->next = new ListNode(x);
            l1 = l1->next;
            l2 = l2->next;
        }

        while(l2 != NULL) {
            x = l2->val + carry_over;
            if (x > 9) {
                carry_over = true;
                x -= 10;
            } else
                carry_over = false;
            l = l->next = new ListNode(x);
            l2 = l2->next;
        }

        if (carry_over)
            l->next = new ListNode(1);

        return head;
    }

};