牛客–链表相加
题目描述
假设链表中每一个节点的值都在 0 – 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
解题思路：
将链表倒置；
区分长链和短链；
以长链为基础将两个链表数值相加，必要时进位；
短链结束后，进位数不为零，则继续遍历长链；
直至进位数为零，若超出长链范围，将进位数生成新节点；
将长链再次倒置；
若有新节点，则置于链表头
返回长链
代码：
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
# @param head1 ListNode类
# @param head2 ListNode类
# @return ListNode类
import copy
class Soution:
def addInList(self, head1, head2):
if head1 == None:
return head2
if head2 == None:
return head1
new=None
g=0
c1,l1=self.reversechains(head1)
c2,l2=self.reversechains(head2) #倒置两个链表
if l1>=l2: #区分链表长度，以长链为基础进行操作
lc=c1
ll=l1
sc=c2
sl=l2
else:
lc=c2
ll=l2
sc=c1
sl=l1
lt=lc #记住链首
st=sl
for i in range(sl): #两个链表对应位置数值相加，超出10进位
tmp=lc.val
lc.val=(tmp+sc.val+g)%10
g=int((tmp+sc.val+g)/10)
lc=lc.next
sc=sc.next
while g!=0: #短链结束后，进位数不为零继续与长链数值相加
if lc!=None:
tmp=lc.val
lc.val=(tmp+g)%10
g=int((tmp+g)/10)
lc=lc.next
else:
new=ListNode(g) #若长链结束，进我数值不为0，则生成新节点
g=0
p,q=self.reversechains(lt) #长链再次倒置
if new==None: #无新节点之间返回
return p
else: #有新节点，则置于链首，返回
new.next=p
return new
def reversechains(self, head): #倒置链表，
nlength=1
cur = head
tmp = head.next
ferr = copy.deepcopy(tmp)
cur.next = None
while tmp != None:
tmp.next = cur
cur = tmp
tmp = ferr.next
ferr = copy.deepcopy(tmp)
nlength=nlength+1
return cur ,nlength #返回倒置链表及长度
用例：
lista=[5,9,2,3,7,4,9,9,0,2,6,6,1,3,8,3,2,1,9,8,4,3,1,3,3,7,5,3,9,3,1,3,1]
listb= [4,2,8,3,5,1,0,5,7,4,5,0,2,5,0,3,9,7,3,6,8,4,4,9,7,1]
s=ListNode(lista[0])
t=s
b=ListNode(listb[0])
a=b
v=copy.deepcopy(b)
for i in range(1,len(lista)):
t.next=ListNode(lista[i])
t=t.next
for j in range(1,len(listb)):
a.next=ListNode(listb[j])
a=a.next
h=Soution()
p=h.addInList(s,b)
while p!=None:
print(p.val)
p=p.next
输出：5 9 2 3 7 5 0 3 3 1 0 1 2 4 4 0 6 7 0 0 9 3 5 3 1 1 2 2 3 8 1 0 2
结果： 牛客只通过25%用例，未返回具体失败的用例；
哪里有问题！？
请高手指教！！
