#左耳听风 ARST 打卡活动重启#
目录
一、题目
二、解题方法一
三、解题方法二
关于 ARTS 的释义 —— 每周完成一个 ARTS：
● Algorithm: 每周至少做一个 LeetCode 的算法题
● Review: 阅读并点评至少一篇英文技术文章
● Tips: 学习至少一个技术技巧
● Share: 分享一篇有观点和思考的技术文章
希望通过此次活动能聚集一波热爱技术的人，延续好奇、探索、实践、分享的精神。
一、题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
二、解题方法一
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef addTwoNumbers(l1, l2):carry = 0p1 = l1p2 = l2ans = Nonewhile p1 or p2 or carry:v1 = p1.val if p1 else 0v2 = p2.val if p2 else 0total = v1 + v2 + carryif total >= 10:carry = 1total %= 10else:carry = 0node = ListNode(total)node.next = ansans = nodeif p1: p1 = p1.nextif p2: p2 = p2.nextreturn ans
其中，`ListNode` 是链表节点的类定义，包含一个值 `val` 和一个指向下一个节点的指针 `next`。`addTwoNumbers()` 函数接受两个链表 `l1` 和 `l2`,并返回它们的和表示的链表。在函数中，我们使用三个指针 `p1`、`p2` 和 `carry` 分别指向两个链表的当前节点和进位值。然后，我们循环遍历两个链表，每次将当前节点的值相加再加上进位值，得到一个新的总和。如果总和大于等于 10,则需要进位；否则不需要进位。最后，我们将新的总和封装成一个节点，并将其插入到结果链表的最前面。当遍历完两个链表后，返回结果链表即可。
具体实现过程如下：
- 定义一个链表节点类
ListNode,包含一个值val和一个指向下一个节点的指针next。- 定义函数
addTwoNumbers(l1, l2),其中l1和l2分别表示两个链表。- 在函数中定义三个指针变量
p1、p2和carry,分别指向两个链表的当前节点和进位值。初始时，p1和p2分别指向两个链表的头节点，carry初始化为 0。- 进入循环，每次循环处理两个链表中的一个节点和一个进位值：
- 首先，获取当前节点的值
v1和进位值v2,如果当前节点为空，则将其值设为 0。- 然后，计算新的总和
total,即v1 + v2 + carry。如果总和大于等于 10,则需要进位；否则不需要进位。- 如果需要进位，则将
carry置为 1,并将总和对 10 取余数，以保证结果不超过 9。- 否则，将
carry置为 0。- 然后，创建一个新的节点
node,其值为total,并将其插入到结果链表的最前面。同时更新指针变量p1、p2和ans,使其分别指向新插入的节点、原链表的下一个节点和当前节点所指向的节点。- 当遍历完两个链表后，返回结果链表即可。
需要注意的是，这个算法的时间复杂度为 O(max(m, n)),其中 m 和 n 分别表示两个链表的长度。因为在最坏情况下，我们需要遍历较长的链表才能得到最终结果。
三、解题方法二
除了使用哈希表来存储已经遍历过的元素及其对应的下标的方法，还可以使用迭代的方式来实现。
具体实现过程如下：
1. 定义一个函数 `addTwoNumbers(l1, l2)`,其中 `l1` 和 `l2` 分别表示两个链表。
2. 在函数中定义两个变量 `num1` 和 `num2`,分别表示第一个链表的当前节点所指向的数字和第二个链表的当前节点所指向的数字。初始时，`num1` 和 `num2` 都为 0。
3. 定义一个变量 `carry`,用于记录进位值。初始时，`carry` 为 0。
4. 进入循环，每次循环处理两个链表中的一个节点：
* 首先，获取当前节点所指向的数字 `val`,如果当前节点为空，则将其值设为 0。
* 然后，将 `num1` 加上 `val`,并将结果与 `num2` 相加，同时加上进位值 `carry`。如果相加的结果大于等于 10,则需要进位；否则不需要进位。
* 如果需要进位，则将 `carry` 置为 1,并更新 `num1` 的值为相加结果对 10 取余数。
* 否则，将 `carry` 置为 0,并更新 `num1` 的值为相加结果。
5. 当遍历完两个链表后，返回一个新的链表，其头节点为 `num1`,尾节点为空。需要注意的是，这个算法的时间复杂度为 O(max(m, n)),其中 m 和 n 分别表示两个链表的长度。因为在最坏情况下，我们需要遍历较长的链表才能得到最终结果。
class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef addTwoNumbers(l1, l2):num1, num2, carry = 0, 0, 0res = ListNode()p1 = l1p2 = l2while p1 or p2 or carry:val1 = p1.val if p1 else 0val2 = p2.val if p2 else 0total = val1 + val2 + carryif total >= 10:carry = 1total %= 10else:carry = 0node = ListNode(total)node.next = res.nextres.next = nodenum1 = val1num2 = val2p1 = p1.next if p1 else Nonep2 = p2.next if p2 else Nonereturn res.next
其中，
ListNode是链表节点的类定义，包含一个值val和一个指向下一个节点的指针next。addTwoNumbers()函数接受两个链表l1和l2,并返回它们的和表示的链表。在函数中，我们使用三个变量num1、num2和carry分别表示第一个链表的当前节点所指向的数字、第二个链表的当前节点所指向的数字和进位值。初始时，num1、num2和carry都为 0。然后，我们进入循环，每次循环处理两个链表中的一个节点和一个进位值：首先获取当前节点所指向的数字val,如果当前节点为空，则将其值设为 0;然后将num1加上val,并将结果与num2相加，同时加上进位值carry;如果相加的结果大于等于 10,则需要进位；否则不需要进位；如果需要进位，则将carry置为 1,并更新num1的值为相加结果对 10 取余数；否则，将carry置为 0,并更新num1的值为相加结果。最后，将新节点插入到结果链表的最前面，并返回结果链表即可。
