struct ListNode 
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


ListNode *AddTwoNumbers(ListNode *l1, ListNode *l2) 
{
    if (!l1) return l2;
    if (!l2) return l1;

    int val = l1->val + l2->val;
    bool carried = (val>9);
    ListNode* head = new ListNode(val%10);
    ListNode* p =head;

    l1 = l1->next;
    l2 = l2->next;

    //add up number in each node
    while(l1 && l2)
    {
        val = l1->val + l2->val + (carried? 1 : 0);
        carried = (val > 9);
        p->next = new ListNode(val%10);

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

    //Add up the remain numbers with carried
    ListNode* remain = l1? l1 : l2;
    while(remain)
    {
        val = remain->val + (carried? 1 : 0);
        carried = (val > 9);
        p->next = new ListNode(val%10);

        p = p->next;
        remain=remain->nex;
    }
    
    //if there still has carried, add '1'
    if (carried)p->next = new ListNode(1);

    return head;
}