document.write('方法一：整数相加法
主要思路：分别遍历两个链表，求出两个链表所代表的整数的值，然后把这两个整数进行相加，最后
把它们的和用链表的形式表示出来。这种方法的优点是计算简单，但是有个非常大的缺点：当链表所代
表的数很大的时候(超出了long的表示范围)，就无法使用这种方法了。
方法二：链表相加法
主要思路：对链表中的结点直接进行相加操作，把相加的和存储到新的链表中对应的结点中，同时还
要记录结点相加后的进位。如下图所示：
使用这种方法需要注意如下几个问题：(1)每组结点进行相加后需要记录其是否有进位；(2)如果两个
链表h1与h2的长度不同(长度分别为L1和L2，且L1＜L2)，当对链表的第L1位计算完成后，接下来只需
要考虑链表L2剩余的结点的值(需要考虑进位)；(3)对链表所有结点都完成计算后，还需要考虑此时是否
还有进位，如果有进位，则需要增加新的结点，此结点的数据域为1。实现代码如下：
class LNode:
def __new__(self,x):
self.data=x
self.next=None
"""
方法功能:对两个带头结点的单链表所代表的数相加
输入参数:h1: 第一个链表头结点; h2: 第二个链表头结点
返回值:相加后链表的头结点
"""
def add(h1,h2):
if h1 is None or h1.next is None:
return h2
if h2 is None or h2.next is None:
return h1
c=0 #用来记录进位
sums=0 #用来记录两个结点相加的值
p1=h1.next #用来遍历h1
p2=h2.next #用来遍历h2
tmp=None #用来指向新创建的存储相加和的结点
resultHead=LNode()#相加后链表头结点
resultHead.next=None
p=resultHead#用来指向链表resultHead最后一个结点
while p1 is not None and p2 is not None:
tmp=LNode()
tmp.next=None
sums=p1.data+p2.data+c
tmp.data=sums%10 #两结点相加和
c=sums/10 #进位
p.next=tmp
p=tmp
p1=p1.next
p2=p2.next
# 链表h2比h1长,接下来只需要考虑h2剩余结点的值
if p1 is None:
while p2 is not None:
tmp=LNode()
tmp.next=None
sums=p2.data+c
tmp.data=sums% 10
c=sums/10
p.next=tmp
p=tmp
p2=p2.next
# 链表h1比h2长,接下来只需要考虑h1剩余结点的值
if p2 is None:
while p1 is not None:
tmp=LNode()
tmp.next=None
sums=p1.data+c
tmp.data=sums%10
c=sums/10
p.next=tmp
p=tmp
p1=p1.next
# 如果计算完成后还有进位,则增加新的结点
if c=1:
tmp=LNode()
tmp.next=None
tmp.data=1
p.next=tmp
return resultHead
if __name__="__main__":
i=1
head1=LNode()
head1.next=None
head2=LNode()
head2.next=None
tmp=None
cur=head1
addResult=None
# 构造第一个链表
while i＜7:
tmp=LNode()
tmp.data=i+2
tmp.next=None
cur.next=tmp
cur=tmp
i+=1
cur=head2
# 构造第二个链表
i=9
while i＞4:
tmp=LNode()
tmp.data=i
tmp.next=None
cur.next=tmp
cur=tmp
i-=1
print "\\nHead1:",
cur=head1.next
while cur is not None:
print cur.data,
cur=cur.next
print "\\nHead2:",
cur=head2.next
while cur is not None:
print cur.data,
cur=cur.next
addResult=add(head1,head2)
print "\\n相加后:",
cur=addResult.next
while curis not None:
print cur.data,
cur=cur.next
程序的运行结果为：
Head1：3 4 5 6 7 8
Head2：9 8 7 6 5
相加后：2 3 3 3 3 9
运行结果分析：
前五位可以按照整数相加的方法依次从左到右进行计算，第五位7+5+1(进位)的值为3，进位为1。此
时head2已经遍历结束，由于head1还有结点没有被遍历，所以，依次接着遍历head1剩余的结点：
8+1(进位)=9，没有进位。因此，运行代码可以得到上述结果。
算法性能分析：
由于这种方法需要对两个链表都进行遍历，因此，时间复杂度为O(N)，其中，N为较长的链表的长
度，由于计算结果保存在一个新的链表中，因此，空间复杂度也为O(N)。
');
![\"360截图20190815224802301.jpg\"](\"http://www.alatiku.com/d/file/shiti/c11ec5ea05422bbd64bb4627a8d0cf5a.jpg\")