问题描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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
- 题目数据保证列表表示的数字不含前导零
思路分析
- 首先，检查特殊情况。如果其中一个链表为空，直接返回另一个链表。这是为了处理其中一个链表为空的边界情况。
- 然后，创建一个哑结点(dummy)作为结果链表的头节点，并创建一个当前节点指针(curr)用于逐个链接新的节点。
- 接下来，需要考虑进位问题。创建一个变量carry，用于记录当前的进位值，初始值为0。
- 然后，开始遍历两个链表，同时处理进位。遍历过程中，我们需要同时访问两个链表的当前节点，并将其值加上进位值，得到一个新的节点值。如果某个链表已经遍历完了，我们可以将其缺失的位数视为0。
- 在每一位数字相加后，需要更新carry变量。当两个数的和超过9时，carry等于1，否则carry等于0。我们可以使用除法运算符和取模运算符进行计算。
- 将新的节点插入结果链表中，并将当前节点指针后移一位。注意，我们需要使用"curr.next"来链接新的节点，并将当前节点指针更新为新的节点。
- 继续遍历两个链表，直到其中一个链表遍历完或者两个链表都遍历完为止。这样可以确保将两个链表的所有位数都相加到结果链表中。
- 检查是否还有进位需要处理。如果carry大于0，说明还有进位，需要将其作为新的节点添加到结果链表的末尾。
- 最后，返回结果链表的头节点(dummy.next)，即可得到表示和的链表。
- 通过遍历两个逆序链表，逐位相加，并处理进位问题，实现了将两个非负整数相加的功能。
代码分析
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)
详细分析
class Solution(object):：定义了一个名为Solution的类，继承自object。def addTwoNumbers(self, l1, l2):：定义了一个名为addTwoNumbers的方法，它接受self（表示当前对象）以及两个参数l1和l2（两个链表）。"""和"""之间的内容是方法的文档字符串，用于描述方法的功能和参数。if not l1: return l2和if not l2: return l1：检查特殊情况。如果其中一个链表为空，直接返回另一个链表作为结果。dummy = ListNode(0)：创建一个值为0的哑结点，用于表示结果链表的头节点。curr = dummy：将curr指针指向哑结点，用于逐个链接新的节点。carry = 0：初始化进位值为0。while l1 or l2:：开始遍历两个链表，循环条件为两个链表中至少有一个未遍历完。x = l1.val if l1 else 0和y = l2.val if l2 else 0：获取当前节点的值，并处理链表已经遍历完的情况。如果链表已经遍历完，将当前节点的值视为0。sum = x + y + carry：计算当前位置的两个节点值以及进位的和。carry = sum // 10：更新进位值，如果和大于等于10，则进位为1；否则进位为0。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：返回结果链表的头节点(dummy.next)。
完结
