题目
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
题目(中文)
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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]
知识点
知识点5：Python 中的对象和引用:
在 Python 中,一切都是对象,包括数字、字符串、列表、字典等。
当你创建一个对象时,Python 会在内存中分配空间来存储该对象。变量实际上是对象的引用,它们存储了对象在内存中的地址。
当你将一个变量赋值给另一个变量时,实际上是创建了一个新的引用,指向同一个对象。
通过引用,你可以访问和操作对象,但你不能直接访问内存地址。
在 Python 中,对象可以分为可变对象和不可变对象两种类型。
不可变对象:一旦创建,其内容就不能被修改。例如,数字、字符串、元组等都是不可变对象。
当你对一个不可变对象进行操作时,实际上会创建一个新的对象,而原对象保持不变。
因为不可变对象的内容不能被修改,所以它们可以安全地被多个引用共享。
可变对象:创建后,其内容可以被修改。例如,列表、字典、集合等都是可变对象。
当你修改一个可变对象时,所有引用该对象的变量都会受到影响,因为它们引用的是同一个对象。
可变对象提供了更大的灵活性,但在多个引用共享时需要小心,以避免意外的修改。
扩展了解：Python的对象和引用、Python的深拷贝和浅拷贝
知识点6：为什么在 Python 中还要实现单链表:
- 虽然 Python 内置的列表(list)已经提供了很多链表的功能,但实现单链表仍有其教育意义。
- 通过自己实现单链表,你可以更深入地理解链表的工作原理和内部结构。
- 实现单链表可以加强咱们初学者对数据结构和算法的理解,学习面向对象的程序设计思路，提高编程技能。 在某些特定情况下,自定义的单链表可能比
- Python 列表更灵活或更高效。（特别是频繁的插入删除这种操作）
知识点7：Python 不能直接访问内存地址吗:
与 C/C++ 等低级语言不同,Python 是一种高级编程语言,它提供了更高层次的抽象。
Python 通过引用来访问对象,而不是直接操作内存地址。你可以认为通过id()函数可以打印出内存地址，但是这也是不一定的。根据 Python 的官方文档,
id() 函数返回一个对象的"标识值"。这个标识值保证在对象的生命周期内是唯一且恒定的。在CPython中的实现就是内存地址。但是实际情况下它真实的内存地址是可能因为一些优化的原因产生移动的。不过我们都使用了Python开发了，也不用太需要知道关于内存细节的事情。有个了解即可。
Python如何实现单链表
leetcode官网已经给出实现，通过定义一个单链表的类，通过属性val和next实现了单链表的功能。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
思路分析
初出茅庐
新建一个l3的链表，
然后遍历完l1和l2的值，l1和l2逐位相加，l3的值逐位更新。
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
l3 = ListNode(0) # 咱们新建一个链表
curr = l3 # 然后我需要一个‘光标’来不断更新我的l3的值
while l1 or l2: #我的循环条件就是遍历完l1和l2，就结束
v1 = l1.val # 获取l1节点值
v2 = l2.val # 获取l2节点值
v3=v1+v2 # 计算两数之和
curr.val=v3# 把v3的值给当前的curr.val
curr=curr.next # 节点后移
l1=l1.next # l1节点后移
l2=l2.next # l2节点后移
return l3
我们作为菜鸟程序员很可能有这样朴素的思路，甚至觉得自己写的代码真是太简洁 ，太优雅，太pythonic的错觉，这可能导致你日后在软件开发中写的代码出现严重问题，就像下面这样：
今天我们就来一起学习编程几个很重要的基本功，（或者咱们就叫基础技能吧，让咱们的代码练习之旅更有种培养角色，我独自升级的幻觉），这两个技能名字叫空值检查和边界条件，然后我们再来看看我们的代码有什么问题。
1技能 空值检查:
空值检查是指在程序中检查变量或对象是否为空(null或undefined)的过程。在许多编程语言中,如果试图访问或操作一个空值,就会导致程序出错或崩溃。因此,在使用`变量或对象之前,特别是当它们来自外部输入或函数返回时,进行空值检查非常重要!!!
各位道友需要注意的问题:
- 在访问变量或对象的属性或方法之前,始终进行空值检查。
- 在进行函数调用时,检查传入的参数是否可能为空值。
- 在进行数据库查询或文件操作时,检查返回的结果是否可能为空。
- 合理地处理空值情况,如提供默认值、抛出异常或给出相应的错误提示
2技能 边界条件:
边界条件是指程序在执行过程中可能遇到的极端或异常情况。这些情况通常发生在输入数据的边界、循环的起始和终止条件、递归的基本情况等。如果没有正确处理边界条件,程序可能会出现意外行为,如死循环、缓冲区溢出、数组下标越界等。
各位道友需要注意的问题:
- 考虑更加全面的测试用例，仔细分析可能的边界条件,如输入数据的最小值、最大值、特殊字符等。
- 在循环和递归中,正确设置起始条件、终止条件和迭代过程。
- 对于数组或集合的操作,检查下标是否越界,特别是在循环中。
- 在进行数值计算时,注意可能出现的除以零、整数溢出等情况。
筑基初期
现在来看看我们的代码存在哪些问题：
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
l3 = ListNode(0) # 咱们新建一个链表
curr = l3 # 然后我需要一个‘光标’来不断更新我的l3的值 # 这里的是对象的引用，没有空值问题
while l1 or l2: #我的循环条件就是遍历完l1和l2，就结束 # 事实上l1和l2长度不一致的时候，下面的赋值就存在为空的可能。
v1 = l1.val # 获取l1节点值 # 看这里！！
v2 = l2.val # 获取l2节点值 # 看这里！！
v3=v1+v2 # 计算两数之和 # 而数值和空的加运算一定会在这里报错！
# 后面待会儿再看
# curr.val=v3# 把v3的值给当前的curr.val
# curr=curr.next # 节点后移
# l1=l1.next # l1节点后移
# l2=l2.next # l2节点后移
return l3
如前所述，当l1或l2为空时,访问l1.val或l2.val可能会导致AttributeError。因此,我们需要在访问之前进行空值检查。
即：
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
l3 = ListNode(0) # 咱们新建一个链表
curr = l3 # 然后我需要一个‘光标’来不断更新我的l3的值 # 这里的是对象的引用，没有空值问题
while l1 or l2: #我的循环条件就是遍历完l1和l2，就结束 # 事实上l1和l2长度不一致的时候，下面的赋值就存在为空的可能。
v1 = l1.val if l1 else 0 # 获取l1节点值,如果为空则为0
v2 = l2.val if l2 else 0 # 获取l2节点值,如果为空则为0
# 实际上在以后得工程环境下，可能你还需要类似int(l1.val)这样的类型转换或者类型判断等操作。
v3=v1+v2 # 计算两数之和 # 前面做了处理，所以这里v3可以正常进行计算，
curr.val=v3# 把v3的值给当前的curr.val # 到这里想想会有问题吗？
curr=curr.next # 节点后移
l1=l1.next # l1节点后移
l2=l2.next # l2节点后移
return l3
接着我们继续检查我们的代码curr.val=v3 curr=curr.next这里会有问题吗？
你真是小天才！是的，这里也是存在空值问题的，聪明的道友你一定发现了对吧！！
第一次循环curr.val=v3看上去人畜无害，但是后面一句，因为在我们的链表实现中默认ListNode.next设置为空了，这就导致curr=curr.next后(在图中第65行代码所示），curr就变成了空值None，我们的这句指令curr.val=v3变成了None.val=v3 把一个值赋值给None的属性val，编译器头都麻了。所以这里也是抛出了错误，‘NoneType’ object has no attribute ‘val’（空值类型对象没有val属性）
所以我们需要先通过把v3这个值放到节点里，然后直接让curr.next指向这个节点。沿用带头结点的单链表的思路，（如果你不用带头结点的单链表思路的话，l3链表的第一个节点需要把ListNode(v3)存储在curr.val中，而后续的节点是存储在curr.next中，这带来了额外的逻辑处理，通过一个带头结点的单链表，我们就不需要对第一个节点单独处理了，直接赋值给curr.next，最后返回链表地址的时候也返回l3.next即可）实现代码如下，
curr.next=ListNode(v3)# 把v3的值给当前的curr.next
curr=curr.next # 节点后移
现在再来看看我们的代码
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
l3 = ListNode(0) # 咱们新建一个链表
curr = l3 # 然后我需要一个‘光标’来不断更新我的l3的值 # 这里的是对象的引用，没有空值问题
while l1 or l2: #我的循环条件就是遍历完l1和l2，就结束 # 事实上l1和l2长度不一致的时候，下面的赋值就存在为空的可能。
v1 = l1.val if l1 else 0 # 获取l1节点值,如果为空则为0
v2 = l2.val if l2 else 0 # 获取l2节点值,如果为空则为0
# 实际上在以后得工程环境下，可能你还需要类似int(l1.val)这样的类型转换或者类型判断等操作。
v3=v1+v2 # 计算两数之和 # 前面做了处理，所以这里v3可以正常进行计算，
curr.next=ListNode(v3)# 把v3的值用ListNode包起来，然后挂给curr.next
curr=curr.next # 节点后移
# 现在我们看看这里有没有问题？
l1=l1.next # l1节点后移
l2=l2.next # l2节点后移
return l3
注意这两句看看有问题吗
是的！这里依然有空值问题，
当l1和l2链表长度不一致的时候，while循环仍在继续，而短的链表已经是空了，这样下面在执行·l=l.next时候，就会进入和之前一样的问题，l=None.next，我们访问了空值类型的属性next
所以我们要避免对None.next的访问，只在l1或l2存在的时候才进行对.next的访问,修改如下:
l1 = l1.next if l1 else None # 在l1不为空的情况下，l1向后移, 如果为空则为空
l2 = l2.next if l2 else None # 在l2不为空的情况下，l2向后移, 如果为空则为空
现在再来看看我们的代码咋样了.
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
l3 = ListNode(0) # 咱们新建一个链表
curr = l3 # 然后我需要一个‘光标’来不断更新我的l3的值 # 这里的是对象的引用，没有空值问题
while l1 or l2: #我的循环条件就是遍历完l1和l2，就结束 # 事实上l1和l2长度不一致的时候，下面的赋值就存在为空的可能。
v1 = l1.val if l1 else 0 # 获取l1节点值,如果为空则为0
v2 = l2.val if l2 else 0 # 获取l2节点值,如果为空则为0
# 实际上在以后得工程环境下，可能你还需要类似int(l1.val)这样的类型转换或者类型判断等操作。
v3=v1+v2 # 计算两数之和 # 前面做了处理，所以这里v3可以正常进行计算，
curr.next=ListNode(v3)# 把v3的值给当前的curr.val
curr=curr.next # 节点后移
l1 = l1.next if l1 else None # l1向后移,如果为空则为空
l2 = l2.next if l2 else None # l2向后移,如果为空则为空
return l3.next
提交运行!
错误回答!
太好了!!我们的代码通过了编译!!!
开个小玩笑,道友们,我们要看到积极的部分,不要因为wrong answer而气馁. 我们来学习下一个基本技能边界条件
看看我们报错的case.
因为4+6=10,
边界条件:
这段代码还有一些边界条件没有考虑:
根据题目条件,两个链表中的每个节点值都在0到9之间。当我们将两个节点的值相加时,结果v3可能会大于等于10,即出现进位。因此,我们需要将v3拆分为个位和十位两部分。
具体来说,我们可以使用整除和取余操作来实现这一点:
个位值 = v3 % 10,即v3除以10的余数
十位值(进位值) = v3 // 10,即v3除以10的商
然后,我们将个位值封装到l3的当前节点的val属性中,表示当前位的计算结果。而十位值则赋给carry变量,用于下一步的计算。
修改代码如下
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
l3 = ListNode(0) # 咱们新建一个链表
curr = l3 # 然后我需要一个‘光标’来不断更新我的l3的值 # 这里的是对象的引用，没有空值问题
carry = 0 # 用来存储进位
while l1 or l2: #我的循环条件就是遍历完l1和l2，就结束 # 事实上l1和l2长度不一致的时候，下面的赋值就存在为空的可能。
v1 = l1.val if l1 else 0 # 获取l1节点值,如果为空则为0
v2 = l2.val if l2 else 0 # 获取l2节点值,如果为空则为0
# 实际上在以后得工程环境下，可能你还需要类似int(l1.val)这样的类型转换或者类型判断等操作。
v3=carry+v1+v2 # 从carry作为初始状态,计算两数之和 # 前面做了处理，所以这里v3可以正常进行计算，
curr.next=ListNode(v3 % 10)# 把v3的值给当前的curr.val
carry=v3 // 10
curr=curr.next # 节点后移
l1 = l1.next if l1 else None # l1向后移,如果为空则为空
l2 = l2.next if l2 else None # l2向后移,如果为空则为空
return l3.next
我们再用边界条件的思想检查一下我们的代码, 首次循环,我们通过带头结点的单链表,carry=0的初值设置,和计算carry+v1+v2三者之和, 保持了首次循环和循环期间的逻辑处理一致. 但是在我们的最后一次循环的时候呢. 比如下面这个测试用例.在l1完成最后的计算的时候, while l1 or l2的循环已经结束了. 新的carry没有地方计算.
所以对于最后一次循环,我们需要额外处理, 执行一次判断,while l1 or l2的循环结束后, 我们对carry做一次判断,如过carry大于0就挂在l3的光标curr后面
if carry > 0:
curr.next = ListNode(carry) # 如果最后还有进位,创建一个新节点
最后代码修改如下
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
l3 = ListNode(0) # 咱们新建一个链表
curr = l3 # 然后我需要一个‘光标’来不断更新我的l3的值 # 这里的是对象的引用，没有空值问题
carry = 0 # 用来存储进位
while l1 or l2: #我的循环条件就是遍历完l1和l2，就结束 # 事实上l1和l2长度不一致的时候，下面的赋值就存在为空的可能。
v1 = l1.val if l1 else 0 # 获取l1节点值,如果为空则为0
v2 = l2.val if l2 else 0 # 获取l2节点值,如果为空则为0
# 实际上在以后得工程环境下，可能你还需要类似int(l1.val)这样的类型转换或者类型判断等操作。
v3=carry+v1+v2 # 从carry作为初始状态,计算两数之和 # 前面做了处理，所以这里v3可以正常进行计算，
curr.next=ListNode(v3 % 10)# 把v3的值给当前的curr.val
carry=v3 // 10
curr=curr.next # 节点后移
l1 = l1.next if l1 else None # l1向后移,如果为空则为空
l2 = l2.next if l2 else None # l2向后移,如果为空则为空
if carry > 0:
curr.next = ListNode(carry) # 如果最后还有进位,创建一个新节点
return l3.next
让我们跑起来试试,
Hooray! 我们通过了测试,并且运行速度上击败了80%的人已经是不错的成绩了!
收获满满 , 今天就学习到这里吧!
结丹阶段
可以看到我们对最后一个循环,是接了一个小尾巴上去,这让我们的代码有点难堪,
元婴大能
可以看到我们的速度还不是最快的, 我们如何更快呢,这需要进阶点出 **“分而治之”**的思想
