上次推出这个用Python刷题leetcode系列后，有人喜欢有人厌，毕竟众口难调。这篇用Python实现两数相加。
写猿人学Python教程之余，也写一个leetcode刷题系列。
题目：两数相加（中等难度）
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
两数相加知识点：单向链表
这道题看似是做加法，其实是考察对单向链表的操作能力。首先，我们要看看什么是单向链表。乍一看它跟Python的列表跟相似，其实它有很多不同于列表的特点：
- 链表的链接方向是单向的；
- 对链表的访问要通过从头部开始，依序往下读取；
- 不能像列表那样通过角标访问元素；
- 不能向上访问链表，只能单向向下读取；列表前后访问很方便。
链表的是由一个个节点链接在一起的，每个节点有两部分：
- 第一部分是节点本身的信息；
- 第二部分是下一个节点的信息。
这个结构如下图所示：
链表的结束就是next的值为空（NULL）。到此为止，我们就可以根据单向链表的结构来遍历它了，伪代码如下：
p = head.next
while p:
print(p.data)
p = p.next
用一个节点指针p指向当前节点，如果p不为空则说明当前节点有值，打印该值，然后让p指向当前节点的next，循环往复，直到p为空也就到了链表的尾部，整个链表就遍历完。
两数相加解题思路
了解完单向链表，我们再来看看题目。这道题其实就是实现我们小学学的加法运算：从个位开始，按位相加，满十进一。题目的加数和被加数用链表表示，为什么要用链表表示呢？我们知道，计算机中的整数位数是有限制的，比如C语言中无符号32位二进制整数（unsigned int）最大是2的32次方，64位的是2的64次方，直接两个int相加有可能出现溢出，比如32为整数就不能表示 (2**32 – 1) + 2 这两个数的和。而用链表表示就可以实现任意位数的加法。
但是，Python里面的整数可以很大，到底有多大呢？查了一圈得出结论，基本上确定跟你的内存有关系，你的内存足够大，它的整数就足够大。Python的大整数(bignum)就是C语言实现的突破了int_32, int_64限制的结构体。
大致估算一下 1GB 内存可以表示多大的整数呢？ 1GB 也就是2**30字节，每个字节有8位，一共可以有 2**30 * 8 位(bit) 也就是 8589934592，除去结构体占用些内存，去个零头就算 8000000000，那么这么多二进制位可以表示的整数就是 2**8000000000 这么大！！ 虽然你的内存远远超过了1GB，但是我劝你不要用Python执行下面这条语句：
print(2**8000000000)
在Python里，你可以轻易得到 2**1000000 即 2 的100万次方这个整数（有轻微卡顿，它要算一下），但是一屏占不下，只好接了个 2 的一万次方的图给大家感受一下“大数”：
既然Python可以支持“无限大”的整数，于是就有了这个思路：
思路一：（奇葩型思路）链表 -> 整数相加 -> 链表
（1）分别把两个链表转换成整数，无论链表多长都可以转换为整数（别超过内存），这个转换算法也有两种：
（a）把链表转换为字符串，字符串再转换成整数：
(1->2->3->4) -> ‘1234’ -> ‘4321’ -> 4321
（b）链表按位相加直接转换为整数：
(1->2->3->4) -> 1 + 2*10 + 3*100 + 4*1000 -> 4321
（2）两个整数相加，把和变为链表返回。
有兴趣的童鞋可以实现一下这个思路，主要是练习链表的遍历、字符串反转、字符串转换为链表这几项。
这个思路利用了Python支持大整数的特点。其实这个题目也可以引申一下，“求两个数字字符串表示的整数的和，返回和的字符串”，这个引申可以直接利用这个奇葩思路，当然出题者的初衷应该不在于此。
可能出题者认为下面的思路才算比较正常的：按位相加，满十进一。
思路二：（正常型思路）按位相加，满十进一
这个思路很正常，不做过多解释，直接看代码：
# Definition for singly-linked list.
#class ListNode:
# def __init__(self,x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
root = ListNode(0)
current = root
carry = 0
while l1 or l2:
v1 = v2 = 0
if l1:
v1 = l1.val
l1 = l1.next
if l2:
v2 = l2.val
l2 = l2.next
val = v1 + v2 + carry
carry = val // 10
val = val % 10
tmp = ListNode(val)
current.next = tmp
current = current.next
if carry:
tmp = ListNode(carry)
current.next = tmp
return root.next
代码优化方面，20-22行可以替换为：
carry, val = divmod(v1+v2+carry, 10)
后来看到别人写的更简短的代码，思路一样，行数更少（9行）：
# Definition for singly-linked list.
#class ListNode:
# def __init__(self,x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, li: ListNode, l2: ListNode) -> ListNode:
p1,p2,dum,rem = l1, l2, ListNode(0),0
p = dum
while p1 or p2:
cur = (p1.val if p1 else 0) + (p2.val if p2 else 0) + rem
rem, cur = cur // 10, cur %10
p.next = ListNode(cur)
p,p1,p2 = p.next, p1.next if p1 else p1, p2.next if p2 else p2
if rem: p.next = ListNode(rem)
return dum.next
思路三： 思路二的进阶，支持多个数（不止两个）相加
# Definition for singly-linked list.
#class ListNode:
# def __init__(self,x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1:ListNode, l2: ListNode) -> ListNode:
root = ListNode(0)
current = root
carry = 0
nums = [l1, l2]
while nums:
val = sum(n.val, for n in nums) + carry
carry = val // 10
val = val % 10
tmp = ListNode(val)
current.next = tmp
current = current.next
nums = [n.next for n in nums if n.next]
if carry:
tmp = ListNode(carry)
current.next = tmp
return root.next
估计你已经看出它和思路二的不同了，它用来一个list把加数包装起来，循环中，下一个节点为空就不再放入list，这样当list为空时加数就都遍历到尾部了，循环也就结束。这个“用list封装”的点，可以支持多个链表相加，不管是10个还是100个，都放到list里面去既可以了。
在leetcode上刷题，同一段代码，不同时间提交，测试结果有时候会相差很多，不知道有没有童鞋遇到同样的现象？有可能是服务器的“忙”或“闲”导致的吧，这个不用太计较。要计较的是，不同实现方法带来的效率的不同。
我的公众号：猿人学 Python 上会分享更多心得体会，敬请关注。
***版权申明:若没有特殊说明，文章皆是猿人学 yuanrenxue.con 原创，没有猿人学授权，请勿以任何形式转载。***
说点什么吧...