牛客–鏈表相加
題目描述
假設鏈表中每一個節點的值都在 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%用例，未返回具體失敗的用例；
哪裡有問題！？
請高手指教！！
