算法很重要，但是每天也需要學(xué)學(xué)python，于是就想用python刷leetcode 的算法題，和我一起開始零基礎(chǔ)python刷leetcode之旅吧。

2. Add Two Numbers

image.png

首先過一下python的一些基礎(chǔ)知識(shí)，非小白請(qǐng)直接跳過

鏈表

從提示代碼可以看出這里涉及到單鏈表結(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)或者訪問特定編號(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)鏈表 。鏈表可以在多種編程語言中實(shí)現(xiàn)。

鏈表是數(shù)據(jù)結(jié)構(gòu)中最基本常用的，C++語言中單鏈表是利用指針操作實(shí)現(xiàn)的，python作為面向?qū)ο缶幊痰?，可以使用?chuàng)建一個(gè)ListNode類來實(shí)現(xiàn)鏈表，利用類的屬性引用來代替指針操作。

鏈表

表頭，指針，結(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