Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

tags: linked list, math

题中的链表是由低位连到高位，这样比较方便进位操作，如果原题中给的链表是反向的话，可以在操作前swap一下，输出前再swap回来即可。

9.21.2015update

There is a cleaner solution with fewer codes.

/**
 * 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 dummyHead = ListNode(0);
        ListNode * p1 = l1, * p2 = l2;
        ListNode * q = &dummyHead;//BUG HERE
        int carry = 0;
        while(p1 != NULL || p2 != NULL){
            int x = (p1 != NULL)? p1->val: 0;
            int y = (p2 != NULL)? p2->val: 0;
            int sum = x + y + carry;
            carry = sum / 10;
            sum = sum % 10;
            q->next = new ListNode(sum);
            q = q->next;
            p1 = (p1 != NULL)? p1->next: NULL;
            p2 = (p2 != NULL)? p2->next: NULL;
        }
        if(carry > 0){
            q->next = new ListNode(carry);
        }
        return dummyHead.next;
    }
};

swap范例：

    ListNode *swap(ListNode *l){
        ListNode * p, * n;
        if(l->next == NULL){
            return l;
        }
        else{
            p = l;
            l = l->next;
            p->next = NULL;
            while(l != NULL){
                   n = l->next;
                   l->next = p;
                   p = l;
                   l = n;
            }
        }
        return p;
    }

需要考虑进位overflow的问题，然后考虑链表不等长的情况，最后考虑计算后，仍有进位的情况。

代码：add可以写在main中，我一开始测试swap就又多写了一个函数。

/** 
 * 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) {
        return add(l1, l2);
    }
    ListNode *add(ListNode *l1, ListNode *l2){
        int sum = 0;
        int overflow = 0;
        ListNode * p = NULL;
        ListNode * tail = NULL;
        ListNode * l = NULL;
        while(l1 != NULL && l2 != NULL){
            sum  = l1->val + l2->val + overflow;
            overflow = sum / 10;
            sum = sum % 10;
            if(p == NULL){
                p = tail = new ListNode(sum);
            }
            else{
                tail->next = new ListNode(sum);
                tail = tail->next;
            }
            l1 = l1->next;
            l2 = l2->next;
        }
        if(l1 != NULL){
            l = l1;
        }
        else if(l2 != NULL){
            l = l2;
        }
        while(l != NULL){
            sum = l->val + overflow;
            overflow = sum / 10;
            sum = sum % 10;
            if(p == NULL){
                p = tail = new ListNode(sum);
            }
            else{
                tail->next = new ListNode(sum);
                tail = tail->next;
            }
            l = l->next;
        }
        if(overflow != 0){
            tail->next = new ListNode(overflow);
            overflow = 0;
            tail = tail->next;
        }
        return p;
    }
};