LeetCode第三题：两数相加详解【3/1000 python】

👤作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。

会一些的技术：数据分析、算法、SQL、大数据相关、python

作者专栏每日更新：

LeetCode解锁1000题: 打怪升级之旅

https://blog.csdn.net/cciehl/category_12625714.html

python数据分析可视化：企业实战案例 https://blog.csdn.net/cciehl/category_12615648.html

备注说明：方便大家阅读，欢迎关注公众号 数据分析螺丝钉 回复关键词 【学习资料】领取notebook和代码调试过程，一起打怪升级

当我们在处理数字问题时，往往会直接考虑数学方法。但在计算机科学中，尤其是在数据结构和算法的领域，我们经常需要采取不同的方法。今天，我们将讨论力扣（LeetCode）上的一个受欢迎的问题，“两数相加”。

问题描述

给定两个非空链表，表示两个非负整数。它们的数字以相反的顺序存储，并且每个节点只能存储一位数字。请将两个数相加，并以链表的形式返回结果。例如：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 输出：7 -> 0 -> 8
 解释：342 + 465 = 807.

在这个问题中，链表的每一个节点都包含一个数字，链表的头节点表示数字的最低位。这与我们书写数字的顺序相反（我们通常从左到右书写，最左边是最高位）。

解题思路

模拟手工加法

1. 初始化一个新的链表节点作为返回结果的哑节点。
2. 遍历两个链表，逐位计算和，处理进位。
3. 如果两个链表长度不一，继续遍历较长的链表，直到所有位计算完毕。
4. 检查最后的进位，如果存在，需要在新链表的末尾添加一个节点。

时间复杂度

算法的时间复杂度为 ( O(max(m, n)) )，其中 ( m ) 和 ( n ) 是两个链表的长度。

空间复杂度

空间复杂度为 ( O(max(m, n)) )，最坏的情况是新链表比输入的链表长1（当最高位有进位时）。

代码示例（Python）

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def add_two_numbers(l1: ListNode, l2: ListNode) -> ListNode:
    head = ListNode(0)
    current = head
    carry = 0
    
    while l1 or l2 or carry:
        val1 = (l1.val if l1 else 0)
        val2 = (l2.val if l2 else 0)
        carry, out = divmod(val1 + val2 + carry, 10)
        
        current.next = ListNode(out)
        current = current.next
        
        l1 = (l1.next if l1 else None)
        l2 = (l2.next if l2 else None)
        
    return head.next
# 测试代码
# 创建链表 2 -> 4 -> 3
l1 = ListNode(2, ListNode(4, ListNode(3)))
# 创建链表 5 -> 6 -> 4
l2 = ListNode(5, ListNode(6, ListNode(4)))
# 进行加法运算
result = add_two_numbers(l1, l2)
# 输出结果链表
while result:
    print(result.val, end=" -> ")
    result = result.next

输出代码的最后部分遍历结果链表并打印出来。如果一切正确，你应该看到：

7 -> 0 -> 8 -> 

这表示数字 807，它是 342 和 465 相加的结果。

其他思路

不过，也有其他一些变种方法和优化可以考虑

反转链表后相加: 这种方法首先将两个链表反转，这样头节点就表示最高位，然后像普通数学加法一样从高位到低位进行相加。最后，再将结果链表反转回来。这种方法需要对链表进行额外的反转操作，所以它并不会减少计算量，而且实际上比模拟法更繁琐。

递归方法： 可以使用递归的方式来实现两数相加。递归方法将问题分解为更小的子问题：首先计算当前位的和，然后递归调用函数来计算剩下的位，最后处理进位。

转换为数字相加： 如果链表不是特别长，另一种方法是将链表转换为整数，然后进行加法运算，最后将结果转换回链表。这种方法违背了问题的初衷（考虑大数问题，链表可能表示的整数超出了语言整数类型的范围），但它在面对较小数字时是可行的。

结论

这个问题，模拟手工加法是比较直接简单的方式，我们学到了如何使用链表处理数字，以及如何在不同的数据结构之间转换问题。即使是没有计算机科学背景的人，也可以理解这个解决方案背后的基本逻辑，因为它非常贴近我们日常处理数字的方式。

欢迎关注微信公众号 数据分析螺丝钉