题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

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

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

样例

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

算法1

(模拟) $O(n)$

模拟竖式加法，某一个链表不为空或进位不为0，从个位开始，三个数相加，模10的余数为和，进位除10(为0或1)，一直循环，直到链表为空或进位为0为止。

时间复杂度

扫描一次，时间复杂度为$0(n)$。

C++ 代码

/**
 * 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 *dummy = new ListNode(-1), *cur = dummy;  // dummy为虚拟头结点，cur指向和链表的尾结点
        int t = 0;  // 进位
        while(l1 || l2 || t){  // 某一个链表不为空或进位不为0，一直做
            if(l1) t += l1->val, l1 = l1->next;
            if(l2) t += l2->val, l2 = l2->next;
            cur->next = new ListNode(t % 10);
            t /= 10;
            cur = cur->next;
        }
        cur = dummy->next;  
        delete dummy; dummy = nullptr;  // 释放虚拟头结点
        return cur;  // 返回和链表头结点
    }
};