2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. 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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

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

循环

/**
 * 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 *l2Node = l2, *l1Node = l1;
        ListNode *result = new ListNode(0);
        ListNode *resultNode = result, *tailNode = result;
        while (l1Node != NULL || l2Node != NULL) {
            int sum = 0;
            if (l1Node != NULL)
                sum += l1Node->val;
            if (l2Node != NULL)
                sum += l2Node -> val;
            int moreThan10 = 0;
            if(sum > 9) {
                sum -= 10;
                moreThan10 = 1;
            }
            
            if(resultNode == NULL) {
                resultNode = new ListNode(sum);
            } else {
                resultNode -> val += sum;
                if (resultNode -> val > 9) {
                    resultNode -> val -= 10;
                    if (resultNode -> next == NULL) {
                        resultNode -> next = new ListNode(1);
                    } else {
                        resultNode -> next -> val += 1;
                    }
                }
            }
            
            if(resultNode -> next == NULL) {
                resultNode -> next = new ListNode(moreThan10);
            } 
            tailNode = resultNode;
            cout << tailNode->val << "&&&&"; 
            cout << resultNode -> val;
            resultNode = resultNode -> next;
            if (l1Node != NULL)
                l1Node = l1Node -> next;
            if (l2Node != NULL)
                l2Node = l2Node -> next;
        }
        if (resultNode != NULL &&
            //resultNode -> next != NULL &&
            resultNode -> val == 0) {
            tailNode->next = NULL;
            cout << "~~~~~~~~";
        }
        return result;
    }
};

参考

/**
 * 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* result = NULL;
        
        int sum = 0;
        int overflow = 0;
        
        while (l1 != NULL && l2 != NULL) {
            sum = l1->val + l2->val + overflow;
            overflow = sum / 10;
            sum = sum % 10;
            result = add(result, sum);
            l1 = l1->next;
            l2 = l2->next;
        }

        while (l1 != NULL) {
            sum = l1->val + overflow;
            overflow = sum /10;
            sum = sum % 10;
            result = add(result, sum);
            l1 = l1->next;
        }
        while (l2 != NULL) {
            sum = l2->val + overflow;
            overflow = sum /10;
            sum = sum % 10;
            result = add(result, sum);
            l2 = l2->next;
        }
        
        if (overflow > 0) {
            result = add(result, overflow);
        }

        return result;
    }
    
    ListNode* add(ListNode* list, int val) {
        ListNode* n = (ListNode*) malloc(sizeof(ListNode));
        n->val = val;
        
        if (list == NULL) {
            n->next = NULL;
            list = n;
        } else {
            ListNode* cur = list;
            while (cur->next != NULL) {
                cur = cur->next;
            }
            cur->next = n;
            n->next = NULL;
        }
        return list;
    }
};