题目描述

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

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

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

示例：

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

---

思路解析

手算两数相加时，我们一般采用的方法是从最低位（个位）开始依次计算。首先将个位的两个数字相加。结果小于10，则直接得到加和后的个位结果，大于等于10的情况，进位为1，剩余的数（减去10后的差值）为个位结果。而后以此类推，但是要注意进位为1的情况下，下一次的计算除了该次位数上的数字相加外还要加上进位1，所得到的结果再判断是否满10，并重复整个流程。
因此，算法统一起来，可以把进位初始化为0。则整个循环过程保持一致。

# solution for python3
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        sum_node = ListNode(0)
        carry_value = 0
        curr_node = sum_node
        p, q = l1, l2
        
        while p != None or q != None:
            tmp_value = 0

            if p == None:
                tmp_value = q.val
            elif q == None:
                tmp_value = p.val
            else:
                tmp_value = p.val + q.val

            tmp_value += carry_value

            tmp_node = ListNode(tmp_value % 10)

            curr_node.next = tmp_node
            curr_node = curr_node.next

            carry_value = tmp_value // 10

            if p != None:
                p = p.next
            if q != None:
                q = q.next
        
        if carry_value > 0:
            curr_node.next = ListNode(carry_value)

        return sum_node.next

// solution for 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* res = new ListNode(0);
        ListNode* curr_node = res;

        ListNode* p = l1;
        ListNode* q = l2;

        int carry_value = 0;

        while (p != NULL || q != NULL){
            int x, y;
            x = p? p->val: 0;
            y = q? q->val: 0;

            int sum = x + y + carry_value;

            curr_node->next = new ListNode(sum%10);
            carry_value = sum / 10;
            curr_node = curr_node->next;

            if (p) p = p->next;
            if (q) q = q->next;
        }

        if (carry_value > 0) curr_node->next = new ListNode(carry_value);

        ListNode* head = res;
        res = res->next; delete head;

        return res;
    }
};

在c++的答案中，因为我们每次new出来的对象需要自己手动释放。这里我们需要把最初的节点释放掉。（如果没有释放掉，函数外的调用者没办法手动释放这个节点。

复杂度分析：
时间复杂度O(n)，空间复杂度O(n)。

---

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。