本文共 2886 字，大约阅读时间需要 9 分钟。

LeetCode.jpg

2. 两数相加    给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。    如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。    您可以假设除了数字 0 之外，这两个数都不会以 0 开头。    示例：    输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)    输出：7 -> 0 -> 8    原因：342 + 465 = 807

切题

一、Clarification

1、明确题目

链表、非空、非负的整数、逆序、每个节点只能存储 一位 数字、除了数字 0 之外，不会以 0 开头

2、边界考虑

a、两个链表l1、l2，注意结束的判断

二、Possible Solution

1、迭代

借助哨兵节点，简化处理；

最高位进位单独处理；

循环遍历l1,l2，都结束时跳出循环，计算当前存储位cur_result，以及进位位next_add。

2、递归

由于存在进位，递归函数参数个数为3，包括l1,l2,add_num(进位位)

递归终止条件 l1,l2都为空并且add_num=0(没有进位)，这样将最高位进位的情况看成l1.val = 0 l2.val = 0进行统一处理

Python3

迭代

# @author:leacoder# @des:  迭代——哨兵 两数相加# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:        pre1 = ListNode(None) # 哨兵        pre2 = ListNode(None)        pre1.next = l1        pre2.next = l2        # next_add进位位（cur_val_1+cur_val_2的十位数）, cur_val_1当前加数, cur_val_2当前被加数,        # cur_result当前存储位（cur_val_1+cur_val_2的个位数）        next_add, cur_val_1, cur_val_2, cur_result = 0, 0, 0, 0        result = ListNode(None)        head = result        while (pre1.next is not None) or (pre2.next is not None):            # 注意对于 next 是否为 None 的处理不同            if pre1.next is None:                cur_val_1 = 0            else:                cur_val_1 = pre1.next.val                pre1 = pre1.next            if pre2.next is None:                cur_val_2 = 0            else:                cur_val_2 = pre2.next.val                pre2 = pre2.next            val_sum = cur_val_1 + cur_val_2 + next_add            next_add = val_sum // 10            cur_result = val_sum % 10            node = ListNode(cur_result)            result.next = node            result = result.next        # 最高位进位处理        if next_add != 0:            node = ListNode(next_add)            result.next = node        return head.next

递归

# @author:leacoder# @des:  递归+哨兵 两数相加# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:        return self.addNumbers(l1, l2, 0)        def addNumbers(self, l1: ListNode, l2: ListNode, add_num: int):        if l1 is None and l2 is None and add_num == 0: # 递归终止条件            return None        l1_value = l2_value = 0        if l1 is None:            l1_value = 0        else:            l1_value = l1.val            l1 = l1.next        if l2 is None:            l2_value = 0        else:            l2_value = l2.val            l2 = l2.next        sum_num = l1_value + l2_value + add_num        result = ListNode(sum_num % 10)        result.next = self.addNumbers(l1, l2, sum_num // 10)        return result

GitHub链接：

知乎个人首页：

简书个人首页：

个人Blog:

欢迎大家来一起交流学习

转载地址：https://blog.csdn.net/leacock1991/article/details/101490312 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！