问题描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例1

输入：l1 = [2,4,3], l2 = [5,6,4]

输出：[7,0,8]

解释：342 + 465 = 807.

示例2

输入：l1 = [0], l2 = [0]

输出：[0]

示例 3

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

输出：[8,9,9,9,0,0,0,1]

提示

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

思路分析

1. 首先，检查特殊情况。如果其中一个链表为空，直接返回另一个链表。这是为了处理其中一个链表为空的边界情况。
   
2. 然后，创建一个哑结点(dummy)作为结果链表的头节点，并创建一个当前节点指针(curr)用于逐个链接新的节点。
   
3. 接下来，需要考虑进位问题。创建一个变量carry，用于记录当前的进位值，初始值为0。
   
4. 然后，开始遍历两个链表，同时处理进位。遍历过程中，我们需要同时访问两个链表的当前节点，并将其值加上进位值，得到一个新的节点值。如果某个链表已经遍历完了，我们可以将其缺失的位数视为0。
   
5. 在每一位数字相加后，需要更新carry变量。当两个数的和超过9时，carry等于1，否则carry等于0。我们可以使用除法运算符和取模运算符进行计算。
   
6. 将新的节点插入结果链表中，并将当前节点指针后移一位。注意，我们需要使用"curr.next"来链接新的节点，并将当前节点指针更新为新的节点。
   
7. 继续遍历两个链表，直到其中一个链表遍历完或者两个链表都遍历完为止。这样可以确保将两个链表的所有位数都相加到结果链表中。
   
8. 检查是否还有进位需要处理。如果carry大于0，说明还有进位，需要将其作为新的节点添加到结果链表的末尾。
   
9. 最后，返回结果链表的头节点(dummy.next)，即可得到表示和的链表。
   
10. 通过遍历两个逆序链表，逐位相加，并处理进位问题，实现了将两个非负整数相加的功能。

代码分析

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        if not l1:
            return l2
        if not l2:
            return l1
        dummy = ListNode(0)

这行代码定义了一个名为dummy的哑结点，用于表示结果链表的头节点。

curr = dummy
• 1

这行代码将curr指针指向哑结点，作为当前节点的指针。

carry = 0
• 1

这行代码初始化进位值为0。

while l1 or l2:
    x = l1.val if l1 else 0
    y = l2.val if l2 else 0
    sum = x + y + carry
    carry = sum // 10
    curr.next = ListNode(sum % 10)
    curr = curr.next
    if l1:
        l1 = l1.next
    if l2:
        l2 = l2.next

这段代码使用了循环来遍历两个链表并进行相加。在每一次循环中，根据当前节点是否为空，获取当前节点的值，并处理链表已经遍历完的情况。接着，计算当前位置的两个节点值以及进位的和，并更新进位值。然后，创建新的节点，并将其链接到当前节点的下一个，将当前节点指针后移一位，指向新创建的节点。最后，如果链表还未遍历完，将当前节点指针后移一位。

if carry > 0:
    curr.next = ListNode(carry)

这行代码处理最后的进位，如果最后还有进位，创建新的节点并将其链接到结果链表的末尾。

return dummy.next
• 1

这行代码返回结果链表的头节点(dummy.next)。

完整代码

class Solution(object):  # 定义一个Solution类，继承自object基类
    def addTwoNumbers(self, l1, l2):  # 定义一个addTwoNumbers方法，接受l1和l2两个参数
        if not l1:  # 如果l1为空链表，返回l2
            return l2
        if not l2:  # 如果l2为空链表，返回l1
            return l1
        dummy = ListNode(0)  # 创建一个值为0的哑结点，用于表示结果链表的头节点
        curr = dummy  # 将curr指针指向哑结点，用于逐个链接新的节点
        carry = 0  # 初始化进位值为0
        while l1 or l2:  # 开始遍历两个链表，循环条件为两个链表中至少有一个未遍历完
            x = l1.val if l1 else 0  # 获取当前节点l1的值，如果l1为空，则视为0
            y = l2.val if l2 else 0  # 获取当前节点l2的值，如果l2为空，则视为0
            sum = x + y + carry  # 计算当前位置的两个节点值以及进位的和
            carry = sum // 10  # 更新进位值，如果和大于等于10，则进位为1；否则进位为0
            curr.next = ListNode(sum % 10)  # 创建新的节点，并将其链接到当前节点的下一个
            curr = curr.next  # 将当前节点指针后移一位，指向新创建的节点
            if l1:  # 如果l1还未遍历完，将当前节点指针后移一位
                l1 = l1.next
            if l2:  # 如果l2还未遍历完，将当前节点指针后移一位
                l2 = l2.next
        if carry > 0:  # 如果最后还有进位，创建新的节点并将其链接到结果链表的末尾
            curr.next = ListNode(carry)
        return dummy.next  # 返回结果链表的头节点(dummy.next)

详细分析

1. class Solution(object):：定义了一个名为Solution的类，继承自object。
   
2. def addTwoNumbers(self, l1, l2):：定义了一个名为addTwoNumbers的方法，它接受self（表示当前对象）以及两个参数l1和l2（两个链表）。
   
3. """和"""之间的内容是方法的文档字符串，用于描述方法的功能和参数。
   
4. if not l1: return l2和if not l2: return l1：检查特殊情况。如果其中一个链表为空，直接返回另一个链表作为结果。
   
5. dummy = ListNode(0)：创建一个值为0的哑结点，用于表示结果链表的头节点。
   
6. curr = dummy：将curr指针指向哑结点，用于逐个链接新的节点。
   
7. carry = 0：初始化进位值为0。
   
8. while l1 or l2:：开始遍历两个链表，循环条件为两个链表中至少有一个未遍历完。
   
9. x = l1.val if l1 else 0和y = l2.val if l2 else 0：获取当前节点的值，并处理链表已经遍历完的情况。如果链表已经遍历完，将当前节点的值视为0。
   
10. sum = x + y + carry：计算当前位置的两个节点值以及进位的和。
    
11. carry = sum // 10：更新进位值，如果和大于等于10，则进位为1；否则进位为0。
    
12. curr.next = ListNode(sum % 10)：创建新的节点，并将其链接到当前节点的下一个。
    
13. curr = curr.next：将当前节点指针后移一位，指向新创建的节点。
    
14. if l1: l1 = l1.next和if l2: l2 = l2.next：如果链表还未遍历完，将当前节点指针后移一位。
    
15. if carry > 0: curr.next = ListNode(carry)：如果最后还有进位，创建新的节点并将其链接到结果链表的末尾。
    
16. return dummy.next：返回结果链表的头节点(dummy.next)。

完结