算法很重要赤兴，但是每天也需要學(xué)學(xué)python斗躏，于是就想用python刷leetcode 的算法題禀综，和我一起開始零基礎(chǔ)python刷leetcode之旅吧击胜。
首先過(guò)一下python的一些基礎(chǔ)知識(shí)，非小白請(qǐng)直接跳過(guò)
鏈表
從提示代碼可以看出這里涉及到單鏈表結(jié)構(gòu)桦沉，代碼如下：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
鏈表由于不必須按順序存儲(chǔ)每瞒，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間纯露。
使用鏈表結(jié)構(gòu)可以克服數(shù)組需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)剿骨，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理埠褪。
但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)
同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域浓利，空間開銷比較大。
鏈表最明顯的好處就是钞速，常規(guī)數(shù)組排列關(guān)聯(lián)項(xiàng)目的方式可能不同于這些數(shù)據(jù)項(xiàng)目在記憶體或磁盤上順序贷掖，數(shù)據(jù)的存取往往要在不同的排列順序中轉(zhuǎn)換。鏈表允許插入和移除表上任意位置上的節(jié)點(diǎn)玉工，但是不允許隨機(jī)存取羽资。鏈表有很多種不同的類型：單向鏈表 雙向鏈表 以及 循環(huán)鏈表 。鏈表可以在多種編程語(yǔ)言中實(shí)現(xiàn)遵班。
鏈表是數(shù)據(jù)結(jié)構(gòu)中最基本常用的屠升，C++語(yǔ)言中單鏈表是利用指針操作實(shí)現(xiàn)的，python作為面向?qū)ο缶幊痰南林＃梢允褂脛?chuàng)建一個(gè)ListNode類來(lái)實(shí)現(xiàn)鏈表腹暖，利用類的屬性引用來(lái)代替指針操作。
表頭翰萨，指針脏答，結(jié)點(diǎn)等概念請(qǐng)自行百度。
下面我們創(chuàng)建了一個(gè)節(jié)點(diǎn)類亩鬼，然后編寫了幾個(gè)鏈表操作殖告，包括創(chuàng)建，插入雳锋，刪除黄绩，輸出等。代碼如下：
class ListNode(): # 初始化 構(gòu)造函數(shù)
def __init__(self,value):
self.value=value
self.next=None
def Creatlist(n):
if n<=0:
return False
if n==1:
return ListNode(1) # 只有一個(gè)節(jié)點(diǎn)
else:
root=ListNode(1)
tmp=root
for i in range(2,n+1): # 一個(gè)一個(gè)的增加節(jié)點(diǎn)
tmp.next=ListNode(i)
tmp=tmp.next
return root # 返回根節(jié)點(diǎn)
def printlist(head): # 打印鏈表 （遍歷）
p=head
while p!=None:
print p.value
p=p.next
def listlen(head): # 鏈表長(zhǎng)度
c=0
p=head
while p!=None:
c=c+1
p=p.next
return c
def insert(head,n): # 在n的前面插入元素
if n<1 or n>listlen(head):
return
p=head
for i in range(1,n-1): # 循環(huán)四次到達(dá) 5 （只能一個(gè)一個(gè)節(jié)點(diǎn)的移動(dòng) range不包含n-1）
p=p.next
a=raw_input("Enter a value:")
t=ListNode(value=a)
t.next=p.next
p.next=t
return head
def dellist(head,n): # 刪除鏈表
if n<1 or n>listlen(head):
return head
elif n is 1:
head=head.next # 刪除頭
else:
p=head
for i in range(1,n-1):
p=p.next # 循環(huán)到達(dá) 2次
q=p.next
p.next=q.next # 把5放在3的后面
return head
def main():
print "Create a linklist"
head=Creatlist(7)
printlist(head)
print
print "___________________________"
n1=raw_input("Enter the index to insert")
n1=int(n1)
insert(head,n1)
printlist(head)
print
print "___________________________"
n2=raw_input("Enter the index to delete")
n2=int(n2)
dellist(head,n2)
printlist(head)
if __name__=='__main__': main() # 主函數(shù)調(diào)用
題目
這道題目是要將兩個(gè)單鏈條相加玷过。輸出得到的新鏈條爽丹。
類似加法的原理, 我們從低位（鏈條第一位）開始，同位相加辛蚊，滿10高位+1
ans = ListNode(0)
tmp = ans
tmpsum = 0
while True:
#依次遍歷l1 l2粤蝎，對(duì)應(yīng)位相加
if l1 != None:
tmpsum += l1.val
l1 = l1.next
if l2 != None:
tmpsum += l2.val
l2 = l2.next
tmp.val = tmpsum % 10 # 除10取余作為當(dāng)前位的值
tmpsum //= 10 #除10取整，即高位袋马，作為指針的下個(gè)結(jié)點(diǎn) 進(jìn)行加法運(yùn)算
if l1 == None and l2 == None and tmpsum == 0:
break
tmp.next = ListNode(0)
tmp = tmp.next
return ans
