题目描述

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

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

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

样例

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

算法1

(暴力枚举) $O(n)$

遍历两个list，直到两个list都没有元素。分别去第一个链表的数据为lval，第二个链表的数据为rval。

把lval + rval 以及上一项的进位相加，计算出keep，以及新的进位carry

然后将keep添加到结果链表中

遍历结束，判断carry是否有数值，如果有的话，创建一个新的node添加到结果链表中。

返回结果，game over!

时间复杂度

只遍历一遍，每一次的计算复杂度是O(1)，因此总的复杂度是O(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 *head = NULL;
        ListNode *retval = NULL;
        int lval, rval, sum, keep;
        int carry = 0;
        while (l1 || l2){
            if (l1 != NULL){
                lval = l1->val;
                l1 = l1->next;
            }else{
                lval = 0;
            }
            if (l2 != NULL){
                rval = l2->val;
                l2 = l2->next;
            }else{
                rval = 0;
            }
            //cout << "l: " << lval << " r: " << rval << endl;
            sum = lval + rval + carry;
            keep = sum % 10;
            carry = sum / 10;

            if (retval==NULL){
                retval = new ListNode(keep);
                head = retval;
            }else{
                retval->next = new ListNode(keep);
                retval = retval->next;
            }
        }
        if (carry)
            retval->next = new ListNode(1);

        return head;
    }
};