# 第88期-基础算法：递归 两数相加
Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。
# 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]
初始代码
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class LinkList:
def __init__(self):
self.head=None
def initList(self, data):
while len(data)==0:return None
self.head = ListNode(data[0])
r=self.head
p = self.head
for i in data[1:]:
node = ListNode(i)
p.next = node
p = p.next
return r
def printlist(self,head):
a=[]
if head == None: return []
node = head
while node != None:
a.append(node.val)
node = node.next
return a
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
#在此之间填写代码
if __name__ == '__main__':
print(LinkList().printlist(Solution().addTwoNumbers(LinkList().initList([2,4,3]),LinkList().initList([5,6,4]))))
print(LinkList().printlist(Solution().addTwoNumbers(LinkList().initList([0]),LinkList().initList([0]))))
print(LinkList().printlist(Solution().addTwoNumbers(LinkList().initList([9,9,9,9,9,9,9]),LinkList().initList([9,9,9,9]))))
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 2 解题思路
- 标签：递归
- 根据题意可知链表数字位数是从小到大的
- 因为两个数字相加会产生进位，所以使用i来保存进位。
- 则当前位的值为(l1.val + l2.val + i) % 10
- 则进位值为(l1.val + l2.val + i) / 10
- 建立新node，然后将进位传入下一层。
# 3 解题方法
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class LinkList:
def __init__(self):
self.head=None
def initList(self, data):
while len(data)==0:return None
self.head = ListNode(data[0])
r=self.head
p = self.head
for i in data[1:]:
node = ListNode(i)
p.next = node
p = p.next
return r
def printlist(self,head):
a=[]
if head == None: return []
node = head
while node != None:
a.append(node.val)
node = node.next
return a
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
def dfs(l, r, i):
if not l and not r and not i: return None
s = (l.val if l else 0) + (r.val if r else 0) + i
node = ListNode(s % 10)
node.next = dfs(l.next if l else None, r.next if r else None, s // 10)
return node
return dfs(l1, l2, 0)
if __name__ == '__main__':
print(LinkList().printlist(Solution().addTwoNumbers(LinkList().initList([2,4,3]),LinkList().initList([5,6,4]))))
print(LinkList().printlist(Solution().addTwoNumbers(LinkList().initList([0]),LinkList().initList([0]))))
print(LinkList().printlist(Solution().addTwoNumbers(LinkList().initList([9,9,9,9,9,9,9]),LinkList().initList([9,9,9,9]))))
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
第1-30，39-42行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第31行： 定义函数dfs，其内部变量l，r，i分别代表第一个链表，第二个链表已经他们和的十位数
第32行： 当两个链表都遍历完且十位数也为0时，结束函数递归
第33行： 定义变量s，若链表存在，则加上链表该位置的值，不存在则加0，再加上i的值（即两个数想加大于十时向前进一）
第34行： 定义链表node，为刚才和的个位数
第35行： 链表node的下一个元素进行递归操作，内部变量分别为之前两个链表的后一个元素以及刚刚和的十位数
第36行： 返回链表
第37行： 使用dfs函数对题目中的链表进行操作
代码运行结果为：
# 算法讲解
这里用到了基础算法：递归，简单讲解下这个算法：
什么是递归
程序调用自身的编程技巧称为递归
递归做为一种算法在程序设计语言中广泛应用。
递归算法一般用于解决三类问题：
(1)数据的定义是按递归定义的。（Fibonacci函数）
(2)问题解法按递归算法实现。
(3)数据的结构形式是按递归定义的。
递归函数特征
必须有一个明确的结束条件；
每次进入更深一层递归时，问题规模相比上次递归都应有所减少
相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）。
递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）
# 结构讲解
这里用到了基础结构：链表，简单讲解下这个链表：
链表
链表是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的链接
链表的结构：data为自定义的数据，next为下一个节点的地址。
基本元素
节点：每个节点有两个部分，左边称为值域，存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针。
head:head节点永远指向第一个节点
tail: tail永远指向最后一个节点
None:链表中最后一个节点的指针域为None值
# 4 视频解析
高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码 