打卡力扣题目三

目录

 一、题目

 二、解题方法一

三、解题方法二 

关于 ARTS 的释义 —— 每周完成一个 ARTS：
● Algorithm: 每周至少做一个 LeetCode 的算法题
● Review: 阅读并点评至少一篇英文技术文章
● Tips: 学习至少一个技术技巧
● Share: 分享一篇有观点和思考的技术文章

希望通过此次活动能聚集一波热爱技术的人，延续好奇、探索、实践、分享的精神。
 

 一、题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

 二、解题方法一
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def addTwoNumbers(l1, l2):
    carry = 0
    p1 = l1
    p2 = l2
    ans = None
    while p1 or p2 or carry:
        v1 = p1.val if p1 else 0
        v2 = p2.val if p2 else 0
        total = v1 + v2 + carry
        if total >= 10:
            carry = 1
            total %= 10
        else:
            carry = 0
        node = ListNode(total)
        node.next = ans
        ans = node
        if p1: p1 = p1.next
        if p2: p2 = p2.next
    return 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 = val
        self.next = next
 
def addTwoNumbers(l1, l2):
    num1, num2, carry = 0, 0, 0
    res = ListNode()
    p1 = l1
    p2 = l2
    while p1 or p2 or carry:
        val1 = p1.val if p1 else 0
        val2 = p2.val if p2 else 0
        total = val1 + val2 + carry
        if total >= 10:
            carry = 1
            total %= 10
        else:
            carry = 0
        node = ListNode(total)
        node.next = res.next
        res.next = node
        num1 = val1
        num2 = val2
        p1 = p1.next if p1 else None
        p2 = p2.next if p2 else None
    return 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 的值为相加结果。最后，将新节点插入到结果链表的最前面，并返回结果链表即可。