上一篇:1.TwoSum(兩數(shù)之和)
題目(Medium)
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example：
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
給定兩個(gè)非空鏈表來代表兩個(gè)非負(fù)數(shù)混蔼，位數(shù)按照逆序方式存儲(chǔ)愿卒，它們的每個(gè)節(jié)點(diǎn)只存儲(chǔ)單個(gè)數(shù)字。將這兩數(shù)相加會(huì)返回一個(gè)新的鏈表色查。
你可以假設(shè)除了數(shù)字 0 之外睦柴，這兩個(gè)數(shù)字都不會(huì)以零開頭
腦洞時(shí)間
這個(gè)題其實(shí)求多位數(shù)相加，主要的難點(diǎn)就是進(jìn)位的記錄。還有要注意的有：
1.當(dāng)兩個(gè)鏈表長度不一致時(shí)的遍歷策略窄瘟，要注意較長的鏈表的值相當(dāng)于原值轉(zhuǎn)移
2.當(dāng)個(gè)鏈表都遍歷相加后依然有進(jìn)位，eg:13+89=102趟卸，存儲(chǔ)為[3->1],[9->8],遍歷相加后為:[2->0],此時(shí)8+1+1(上次進(jìn)位)又形成了進(jìn)位蹄葱，需要新增一位[2->0->1](形成的進(jìn)位)]
廢話少說擼代碼
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class LinkList:
def __init__(self):
self.head = None
self.size = 0
def isEmpty(self):
return self.head == None
def length(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.next
return count
def append(self, val):
temp = ListNode(val)
if self.isEmpty():
self.head = temp
else:
current = self.head
while current.next != None:
current = current.next
current.next = temp
def add(self, val):
temp = ListNode(val)
if self.isEmpty():
self.head = temp
else:
temp.next = self.head
self.head = temp
# self.printf()
def printf(self):
if self.isEmpty():
print("NONE")
else:
current = self.head
while current != None:
print(current.val)
current = current.next
class Solution:
# 求當(dāng)前鏈表長度
def length(self, l):
current = l
count = 0
while current != None:
count += 1
current = current.next
return count
def addTwoNumbers(self, l1, l2):
rList = LinkList()
if self.length(l1) >= self.length(l2):
current1 = l1
current2 = l2
count = self.length(l2)
else:
current2 = l1
current1 = l2
count = self.length(l1)
zCount = 0
addFlag = 0
while current1 != None:
#按長表來遍歷
tempVal = current1.val
# 判斷短表是否結(jié)束
if zCount < count:
tempVal = tempVal + current2.val
current2 = current2.next
# 判斷進(jìn)位
if addFlag > 0:
tempVal = tempVal + addFlag
addFlag = 0
# 記錄進(jìn)位
if tempVal >= 10:
tempVal = tempVal - 10
addFlag = 1
rList.append(tempVal)
current1 = current1.next
zCount = zCount + 1
# 鏈表都遍歷相加完后依然有進(jìn)位氏义，新增一位
if addFlag > 0:
rList.append(addFlag)
return rList
def main():
ll1 = LinkList()
ll2 = LinkList()
# 342+465=807
ll1.add(3)
ll1.add(4)
ll1.add(2)
ll2.add(4)
ll2.add(6)
ll2.add(5)
# ll2.add(0)
# l1.printf()
# l2.printf()
l1 = ll1.head
l2 = ll2.head
rl = Solution().addTwoNumbers(l1, l2)
rl.printf()
if __name__ == '__main__':
main()
算法復(fù)雜度
時(shí)間復(fù)雜度為:O(N)，N為較長鏈表的長度图云，即
空間復(fù)雜度為:O(N)
三省吾題
剛開始以為操作的是兩個(gè)鏈表惯悠，寫參數(shù)的時(shí)候就傳了兩個(gè)鏈表。Leetcode運(yùn)行老是報(bào)錯(cuò)竣况，說有些方法沒有定義克婶。仔細(xì)一看，才發(fā)現(xiàn)傳的參數(shù)是節(jié)點(diǎn)指針丹泉，稍作修改乎就Accepted了情萤。
總結(jié)而言，這道題并不難摹恨，主要考察數(shù)據(jù)結(jié)構(gòu)中鏈表的構(gòu)造與遍歷思路很快就有了筋岛，我花費(fèi)的時(shí)間有點(diǎn)長是因?yàn)樵陧槺憔毩?xí)Python的語法〔撬可不要笑話我這個(gè)Python新手……
.
.
.
下一篇:3.無重復(fù)字符的最長子串(LongestSubstringWithoutRepeatingCharacters)
------------------------------20180311夜
刷Leetcode泉蝌，
在我看來，
其實(shí)是為了維持一種編程狀態(tài)揩晴！
