牛客–鏈表相加

題目描述

假設鏈表中每一個節點的值都在 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%用例,未返回具體失敗的用例;
   哪裡有問題!?
   請高手指教!!