leetcode今日每日一题

今日的每日一题是「两数相加」（Add Two Numbers），编号为 2。

题目描述

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

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

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

示例

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

解题思路

本题的难点在于链表的遍历和处理进位。具体思路如下：

- 遍历两个链表，同时记录进位 carry。
- 将两个链表的当前节点的值相加，加上上一轮的进位 carry。
- 计算当前位的值和进位 carry。
- 将当前位的值插入新链表的末尾，并将当前节点指向下一个节点。
- 循环执行步骤 2~4，直到两个链表都遍历完毕。
- 如果最后还有进位，将进位添加到新链表的末尾。

时间复杂度：O(max(m, n))，其中 m 和 n 分别为两个链表的长度。

空间复杂度：O(max(m, n))，新链表的长度为 max(m, n) + 1。

参考代码

以下是 Python3 的实现代码：