/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

#include <string>

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* sum = new ListNode(0);
        int overflow = 0;
        ListNode* init = sum;
        while(l1 != NULL && l2 != NULL){
            overflow = 0;
            sum->val = sum->val + l1->val + l2->val;
            if(l1->val + l2->val > 9){
                overflow = sum->val/10;
                sum->val = sum->val%10;
            }
            if(l1->next != NULL && l2->next != NULL){
                sum->next = new ListNode(overflow);
            }else{
                sum->next = new ListNode(0);
            }

            sum = sum->next;
            l1 = l1->next;
            l2 = l2->next;
        }

        if(overflow != 0){
            if(l1 == NULL && l2 != NULL){
                sum = l2;
                o_f(l2,overflow);
            }else if(l1 != NULL && l2 == NULL){
                sum = l1;
                o_f(l1,overflow);
            }else{
                sum = new ListNode(overflow);
            }
        }

        return init;
    }

    void o_f(ListNode* &L, int overflow){
        int temp = L->val;
        L->val = (L->val + overflow)%10;
        if(temp + overflow > 9){
            if(L->next != NULL){
                o_f(L->next, (temp + overflow)/10);
            }else{
                L->next = new ListNode((temp + overflow)/10);
            }
        }else{
            L = new ListNode(overflow);
        }
    }
};