難度：中等
題目內(nèi)容：
給你兩個 非空 鏈表來代表兩個非負整數(shù)。數(shù)字最高位位于鏈表開始位置。它們的每個節(jié)點只存儲一位數(shù)字。將這兩數(shù)相加會返回一個新的鏈表。
你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)字都不會以零開頭。
進階：
如果輸入鏈表不能修改該如何處理？換句話說，你不能對列表中的節(jié)點進行翻轉(zhuǎn)。
示例：
輸入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 8 -> 0 -> 7
題解:
emmm
首先最簡單的情況就是有數(shù)為0 ，直接返回另一個就好了
其他的情況可以先把列表翻轉(zhuǎn)過來，然后相加的出一個新列表，把新列表再翻轉(zhuǎn)一下就得到結(jié)果了。
不過題目要求不能進行翻轉(zhuǎn)
emmm那也好說，我們加一個位數(shù)計數(shù)就好了
不過要注意的是（反正我出錯了）相加是可能進多位的（199+1這樣）
我下面這個就算初步修改了一下，但是只能解決進兩位。。。所以打算換種方法，先算出來，然后把中間變成兩位的數(shù)拆開就好了嘛，比如10拆成1 0
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
###如果有0的話
if l1.val == 0:
return l2
elif l2.val == 0:
return l1
l1len = 0
l1c = l1
while l1c:
l1c = l1c.next
l1len += 1
l2len = 0
l2c = l2
while l2c :
l2c = l2c.next
l2len += 1
if l2len >= l1len:
return self.sum(l2,l2len,l1,l1len)
elif l2len < l1len:
return self.sum(l1,l1len,l2,l2len)
def sum(self,lbig,lbiglen,lsmall,lsmalllen):
# if lbiglen == lsmalllen and (lbig.val +lsmall.val) >= 10:
# r = ListNode(1)
r0 = ListNode(0)
r = r0
while lbig:
if lbiglen == lsmalllen:
if (lbig.val +lsmall.val) >= 10:
r.val += 1
r.next = ListNode(mod( (lbig.val +lsmall.val) ,10))
if r.next.val == 9:#預警一下會不會連進兩位
temp = r
r = r.next
lbig = lbig.next
lbiglen -= 1
lsmall = lsmall.next
lsmalllen -= 1
else:
r.next = ListNode(lbig.val)
if r.next.val == 9:#預警一下會不會連進兩位
temp = r
r = r.next
lbig = lbig.next
lbiglen -= 1
if r0.val == 0 and r0.next:
r0 = r0.next
return r0
稍加改動，就可以通過啦！
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
###如果有0的話
if l1.val == 0:
return l2
elif l2.val == 0:
return l1
l1len = 0
l1c = l1
while l1c:
l1c = l1c.next
l1len += 1
l2len = 0
l2c = l2
while l2c :
l2c = l2c.next
l2len += 1
if l2len >= l1len:
return self.sum(l2,l2len,l1,l1len)
elif l2len < l1len:
return self.sum(l1,l1len,l2,l2len)
def sum(self,lbig,lbiglen,lsmall,lsmalllen):
# if lbiglen == lsmalllen and (lbig.val +lsmall.val) >= 10:
# r = ListNode(1)
r0 = ListNode(0)
r = r0
while lbig:
if lbiglen == lsmalllen:
if (lbig.val +lsmall.val) >= 10:
r.val += 1
r.next = ListNode(mod( (lbig.val +lsmall.val) ,10))
r = r.next
lbig = lbig.next
lbiglen -= 1
lsmall = lsmall.next
lsmalllen -= 1
else:
r.next = ListNode(lbig.val)
r = r.next
lbig = lbig.next
lbiglen -= 1
if r0.val == 0 and r0.next:
r0 = r0.next
# 拆數(shù)
l = lbiglen
r = r0
carry = True
while carry:
carry = False
r = r0
while r.next:
if r.next.val >= 10:
r.val += 1
r.next.val -= 10
carry = True
r = r.next
# 第一位大于等于10要變成兩個數(shù)
if r0.val >= 10:
newNode = ListNode(mod(r0.val,10))
newNode.next = r0.next
r0.val = r0.val // 10
r0.next = newNode
l += 1
return r0
