題目：

給出兩個(gè) 非空 的鏈表用來表示兩個(gè)非負(fù)的整數(shù)。其中楣责，它們各自的位數(shù)是按照 逆序 的方式存儲的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲 一位 數(shù)字初嘹。

如果沮趣，我們將這兩個(gè)數(shù)相加起來，則會返回一個(gè)新的鏈表來表示它們的和兔毒。

您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會以 0 開頭迅脐。

示例：

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/add-two-numbers

解法一：

首先想到的是使用遞歸來做豪嗽，首先確定終止條件，是否到達(dá)鏈表尾部（l1和l2均到達(dá)）隐锭，并且判斷尾部是否大于10计贰。之后對ListNode進(jìn)行操作。首先補(bǔ)齊l1和l2中較短的鏈表躁倒，之后再相加并判斷是否大于10。

/**
 * 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* l;
        int sum = l1->val + l2->val;
        if(l1->next == NULL && l2->next == NULL){
            if(sum >= 10){
                sum-= 10;
                l = new ListNode(sum);
                l->next = new ListNode(1);
                return l;
            }
            else
                return new ListNode(sum);
        }
            
        else{
            if(l1->next == NULL)
                l1->next = new ListNode(0);
            if(l2->next == NULL)
                l2->next = new ListNode(0);
            if(sum >= 10){
                sum = sum - 10;
                l1->next->val++;
            }
            l = new ListNode(sum);
            l->next = addTwoNumbers(l1->next, l2->next);
            return l;
        }
    }
};

解法二：

但遞歸效率不高褐桌，因此可將其改為循環(huán)迭代來實(shí)現(xiàn)

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if (!l1)
            return l2;
        if (!l2)
            return l1;

        ListNode *node1 = l1;
        ListNode *node2 = l2;
        ListNode *newNode = NULL;
        ListNode *current = NULL;
        int carry = 0;
        while (node1 || node2) {
            int val1 = node1 ? node1->val : 0;
            int val2 = node2 ? node2->val : 0;
            int sum = val1 + val2 + carry;
            int val = sum % 10;
            carry = sum / 10;
            if (!newNode) {
                newNode = new ListNode(val);
                current = newNode;
            }
            else {
                current->next = new ListNode(val);
                current = current->next;
            }
            node1 = node1 ? node1->next : NULL;
            node2 = node2 ? node2->next : NULL;
        }

        if (carry) {
            current->next = new ListNode(carry % 10);
        }

        return newNode;
    }
};