给出两个非空的链表用来表示两个非负的整数。

其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

原因：342 + 465 = 807

C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2)
{
    struct ListNode *t1 = l1;
    struct ListNode *t2 = l2;
    struct ListNode *sum;
    struct ListNode *sum1;
    struct ListNode *sum2;
    while (t1 && t2)
    {
        t1 = t1->next;
        t2 = t2->next;
    }

    if (t1 == NULL)
    {
        sum = l2;
    }
    else
    {
        sum = l1;
    }

    sum1 = sum;
    t1 = l1;
    t2 = l2;
    int move = 0;

    while (sum1)
    {
        int temp = 0;

        if (t1)
        {
            temp = t1->val;
            t1 = t1->next;
        }

        if (t2)
        {
            temp += t2->val;
            t2 = t2->next;
        }

        if (move == 1)
        {
            temp++;
        }

        if (temp >= 10)
        {
            temp -= 10;
            move = 1;
        }
        else
        {
            move = 0;
        }

        sum1->val = temp;
        sum2 = sum1;
        sum1 = sum1->next;
    }

    if (move == 1)
    {
        struct ListNode *xxx = (struct ListNode *)malloc(sizeof(struct ListNode));
        xxx->val = move;
        xxx->next = 0;
        sum2->next = xxx;
    }

    return sum;
}

C++

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        return dfs(l1, l2, 0);
    }

    ListNode* dfs(ListNode* l, ListNode* r, int i) {
        if (!l && !r && !i) return nullptr;
        int sum = (l ? l->val : 0) + (r ? r->val : 0) + i;
        ListNode* node = new ListNode(sum % 10);
        node->next = dfs(l ? l->next : nullptr, r ? r->next : nullptr, sum / 10);
        return node;
    } 
};