python算法--009计算两个链表所代表的整数之和（链表相加
两人对酌山花开，一杯一杯复一杯。——李白《山中与幽人对酌》
李白喝了酒，写的诗这么棒；如果我喝了写代码，那电脑可能会崩溃。
题目：题目：给定两个链表，链表的每一个节点代表一位数，个位数在链表的前面，要求两个链表所代表的整数的和，用一个链表表示出来。例如：head1->1->3->4->5 和 head2->2->1->6->2，所代表的数分别为：54311，26122，=>54311+26122=80433,用链表表示为Head->3->3->4->0->8。
昨天讲的整数相加法好像没几个人看，今天介绍的是链表相加法，那么如何链表相加呢？下面跟我一起来看一下：
一样先来分析一下问题，要求的是链表代表的整数的和，那么不用链表代表的整数和怎么算呢？我给出了几个小栗子：
- 1 + 1 = 2
- 111 + 111 = 222
- 2 + 9 = 11
- 112 + 19 = 131
- 11 + 999 = 1010
- 999,987,654,321 + 9,876,543 = 999,997,530,864
这几个栗子可以代表绝大多数情况(这里不考虑负数)：第一个和第二个，都代表的是长度相等的情况，而且都没有进位；第三个，长度相等，但是有进位；第四个长度不等，有进位，但是最高位没有进位；第五个，长度不等，有进位，且最高位有进位；第六个，这是最长的一个，也是最为常见的情况，我用逗号将他们分开了好让大家看到位数，可以看到这是一个12位数加7位数，我们自己在用笔算的时候是这样一个过程（字丑。。。很久没写字了，更丑了）：
计算过程
我们是以个位对齐，并从个位开始相加，每一位都加。如果大于10，则向前进1。这大家小学都学过。但是到了短的数算完了，也就是遍历到上面的8，这一位是只加了一个进位1，最高的四位，9999是直接加到了和的前面。 当然更规范来说，每一位都加了进位，高位的9999也是都加了进位，但是此时进位为0。对于整数的算法就这样，那我们下面来看，如果是保存在链表里的数怎么办？
我们的链表是将个位保存在了第一位，这与我们的笔算顺序是一致的。用程序语言来说：从链表头开始，每一位相加，并记录是否有进位。将结果的个位存入新的链表对应的位置，然后遍历下一个节点，一样是相加，同时还要加上进位C。过程中如果短的链表加完了，那么短的链表停止遍历，继续遍历长的链表，记得加上进位。当所有的都遍历完了，也要考虑进位，因为，当两个链表长度相同时，加完了是否还有进位。具体详细的我在代码的注释里都写上了，大家仔细看下，注意点还是蛮多的。
我怕代码太长你们不愿意看，我就先放求和函数的代码,这看起来很长，其实只是我注释写的比较多：
#输入两个链表，计算链表代表整数的和，并将其存入链表返回
def function(head1,head2):
#判断两个链表是否都为空为空，为空则返回空链表
if head1.next is None and head2.next is None:
return head1
cur1=head1.next # 指向head1的第一个节点
cur2=head2.next # 指向head2的第一个节点
c=0#用来记录进位
newhead=LNode(None)#这是相加之后产生的新链表，这里称为和
cur=newhead#指向和
#当两个链表至少有一个还没有遍历完时，循环
#这里比较复杂，有三种情况
#（1）当head1遍历完了
#（2）当head2遍历完了
#（3）两个都没有遍历完
while cur1 is not None or cur2 is not None:
#head1遍历完了
if cur1 is None:
#此时head2是有数据的，head1没有，这里注意加上进位
sumL = cur2.data + c
#head2遍历完了
elif cur2 is None:
#此时head1是有数据的，head2没有，这里注意加上进位
sumL = cur1.data + c
# 都没遍历完
else:
#这时两个都有数据，加上进位
sumL = cur1.data + cur2.data + c
#判断是否产生进位
if sumL>=10:
c=1
else:
c=0
#将该位的和的个位存储为一个节点，并接在总和链表的后面
n=sumL%10
tmp=LNode(n)
cur.next=tmp
cur=tmp
#这里是用于循环的语句，这里是需要判断一下的，
#因为，如果有一个链表先遍历完了，也就是短的那条
#此时cur是None，如果运行cur1=cur1.next,会报错
#提示cur为空类型，没有next属性
#所以这里要先判断，如果为空，就不做变化
#前面的循环判断语句while cur1 is not None or cur2 is not None:
#这里我用的 OR 所以要两个都为空才能出循环，这样就省去了判断谁长谁短的步骤了
if cur1 is not None:
cur1=cur1.next
if cur2 is not None:
cur2=cur2.next
# 注意！！！！假如两个链表一样长，最后的一位相加大于10，
# 程序是直接存储了个位，就直接退出了，并没有考虑c进位
# 所以这里单拿出来判断下
if c==1:
tmp=LNode(1)
cur.next = tmp
cur = tmp
#结束后直接返回存储着两个链表的和的链表
return newhead
前面的构造链表我写了很多次，这里就先不放，我放到最后的总代码里，下面我们来验证一下，是否可行，我试了各种情况：
if __name__ == '__main__':
#构造链表，这里可以多试几次，用不同的长度
head1 = creatLink(8)
head2 = creatLink(1)
#打印head1head2
print("head1:")
cur = head1.next
while cur != None:
print(cur.data)
cur = cur.next
print("head2:")
cur = head2.next
while cur != None:
print(cur.data)
cur = cur.next
#调用求和函数
head = function(head1, head2)
#打印和链表
print("\nAfteplus:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
一位加一位：
1+1
空链表加空链表这很重要，很多人的程序都没考虑到这个，都会报错：
0+0
两个长度相同的：
8+8
长度不同的：
8+1
我自己还试过1000000位+1000000位的，时间长了一点，但是没报错，结果也对，理论上，可以算。。。很长的数值相加-,结果太长，我就不贴图了，大家自己试一试。
这是全部的代码，构造链表的代码啥的都在里面：
import random
#定义链表节点类型
class LNode:
"""docstring for LNode"""
def __init__(self, arg):
self.data = arg
self.next = None
"""
题目描述：
将Head->1->1->3->3->5->7->7->8
与head->1->2->5->7->8相加
得Head->2->3->8->0->4->8->7->8
个位在前
方法：链表相加
"""
#构造链表
def creatLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
n = random.randint(0, 9)
tmp = LNode(n)
cur.next = tmp
cur = tmp
i += 1
return head
#输入两个链表，计算链表代表整数的和，并将其存入链表返回
def function(head1,head2):
#判断两个链表是否都为空为空，为空则返回空链表
if head1.next is None and head2.next is None:
return head1
cur1=head1.next # 指向head1的第一个节点
cur2=head2.next # 指向head2的第一个节点
c=0#用来记录进位
newhead=LNode(None)#这是相加之后产生的新链表，这里称为和
cur=newhead#指向和
#当两个链表至少有一个还没有遍历完时，循环
#这里比较复杂，有三种情况
#（1）当head1遍历完了
#（2）当head2遍历完了
#（3）两个都没有遍历完
while cur1 is not None or cur2 is not None:
#head1遍历完了
if cur1 is None:
#此时head2是有数据的，head1没有，这里注意加上进位
sumL = cur2.data + c
#head2遍历完了
elif cur2 is None:
#此时head1是有数据的，head2没有，这里注意加上进位
sumL = cur1.data + c
# 都没遍历完
else:
#这时两个都有数据，加上进位
sumL = cur1.data + cur2.data + c
#判断是否产生进位
if sumL>=10:
c=1
else:
c=0
#将该位的和的个位存储为一个节点，并接在总和链表的后面
n=sumL%10
tmp=LNode(n)
cur.next=tmp
cur=tmp
#这里是用于循环的语句，这里是需要判断一下的，
#因为，如果有一个链表先遍历完了，也就是短的那条
#此时cur是None，如果运行cur1=cur1.next,会报错
#提示cur为空类型，没有next属性
#所以这里要先判断，如果为空，就不做变化
#前面的循环判断语句while cur1 is not None or cur2 is not None:
#这里我用的 OR 所以要两个都为空才能出循环，这样就省去了判断谁长谁短的步骤了
if cur1 is not None:
cur1=cur1.next
if cur2 is not None:
cur2=cur2.next
# 注意！！！！假如两个链表一样长，最后的一位相加大于10，
# 程序是直接存储了个位，就直接退出了，并没有考虑c进位
# 所以这里单拿出来判断下
if c==1:
tmp=LNode(1)
cur.next = tmp
cur = tmp
#结束后直接返回存储着两个链表的和的链表
return newhead
if __name__ == '__main__':
#构造链表，这里可以多试几次，用不同的长度
head1 = creatLink(1000000)
head2 = creatLink(1000000)
#打印head1head2
print("head1:")
cur = head1.next
while cur != None:
print(cur.data)
cur = cur.next
print("head2:")
cur = head2.next
while cur != None:
print(cur.data)
cur = cur.next
#调用求和函数
head = function(head1, head2)
#打印和链表
print("\nAfteplus:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
总结一下，这个算法还是很重要的，因为它可以算很大的数，比昨天的整数相加法要好很多。改一下代码，就能计算很小的数，小数点后面很多位都行；在深入一点，就可以计算很大的数的乘法（按笔算的乘法过程来），计算器没法实现，这样算法就可以派上用场。当然，pythoon有很多强大的模块也可做到。
最近有点忙过头了，但是想想又没做什么。。。。真真是时间都去哪了？今早放洗衣机里的衣服一直没拿出来，还是刚才赶回去拿出来了，立马回来上课。今天上完晚课，就原地开始写文章了，还好没晚太久。明天空了(可能就这一周了，两个老师都想要周五没课的时间，估计是保不住了)，我会好好整理下，刚开学过得稀里糊涂的。
还是那样，我一如既往的乐于帮助大家——微信、简书：Dkider。语句千万条，正确第一条。代码不规范，手指两行泪。
Dkider
这是这首诗的后两句。只能说李白在哪里都很厉害。我李白贼秀。。。
我醉欲眠卿且去，明朝有意抱琴来。 ——李白《山中与幽人对酌》
