上一篇文章也講的單鏈表的逆序，但我沒有詳細(xì)的將過程寫出來望忆。這讓讀者不能夠更加快速的理解我寫的代碼的原理吴叶，是我的疏忽阐虚，以后會(huì)慢慢改進(jìn)。今天看的一篇文章中說蚌卤，“如果我能寫出清晰的注釋和技術(shù)規(guī)格說明書实束，其他程序員能夠理解我的代碼奥秆，因此他們就能在自己的代碼中使用，而不用重寫咸灿。如果我做不到這一點(diǎn)构订，那我的代碼對(duì)其他人就沒有價(jià)值”苁福”看到這話悼瘾，我心里一顫，上一篇文章簡(jiǎn)直就是一坨shi审胸。

好了亥宿，廢話不多說，進(jìn)入正題歹嘹。

題目：給定一個(gè)帶頭節(jié)點(diǎn)的單鏈表：head->1->2->3->4->5->6->7->8箩绍；使其成為：head->8->7->6->5->4->3->2->1孔庭。

這次題目與上次一樣是將單鏈表逆序尺上。鏈表是一種在學(xué)習(xí)、編寫程序等時(shí)用的非常多的數(shù)據(jù)結(jié)構(gòu)圆到。我們這里研究的鏈表是單鏈表怎抛，而單鏈表又有帶頭節(jié)點(diǎn)和不帶頭節(jié)點(diǎn)兩種。

這里給出帶頭節(jié)點(diǎn)的鏈表的建立方法：由N個(gè)節(jié)點(diǎn)鏈在一起的叫鏈表芽淡，當(dāng)節(jié)點(diǎn)只包含自身存儲(chǔ)的數(shù)據(jù)以及其后繼節(jié)點(diǎn)的信息的鏈表叫單鏈表马绝。python中沒有指針的概念，但是引用的功能類似于指針挣菲，所以用引用來建立節(jié)點(diǎn)之間的關(guān)系富稻，為了方便理解，之后的文章可能會(huì)用指針來描述白胀。
節(jié)點(diǎn)的數(shù)據(jù)域用data表示椭赋，其后繼節(jié)點(diǎn)域用next表示：

#先建立節(jié)點(diǎn)對(duì)象LNode
class LNode:
    def __init__(self,arg):
        # 這是數(shù)據(jù)域data
        self.data = arg    
        # 這是節(jié)點(diǎn)的next域，也就是下一個(gè)節(jié)點(diǎn)的引用
        self.next = None  
"""
方法功能：創(chuàng)建一個(gè)帶頭節(jié)點(diǎn)的單鏈表
"""
def creatLink(x):
    #  x是鏈表的長(zhǎng)度 
    i = 1
    head = LNode(None) # 先構(gòu)造單鏈表的頭節(jié)點(diǎn)
    tmp = None # 用來指向新添加的節(jié)點(diǎn)
    cur = head # 用來指向鏈表的最后一個(gè)節(jié)點(diǎn)
    while i <= x:
        tmp = LNode(i)
        cur.next = tmp
        cur = tmp
        i += 1
    return head

這次我們使用遞歸法來實(shí)現(xiàn)： 遞歸程序有兩個(gè)要素：一是遞歸定義或杠，一是遞歸終止條件哪怔。我們先來分析一下，如果要將單鏈表1->2->3->4->5->6->7->8 變成8->7->6->5->4->3->2->1向抢，只需要先把鏈表變成1->8->7->6->5->4->3->2认境，然后在將第一個(gè)節(jié)點(diǎn)1鏈接到鏈表的尾部就行了。但是要實(shí)現(xiàn)1->8->7->6->5->4->3->2挟鸠，就需要先把將節(jié)點(diǎn)1后面的子鏈表逆序叉信。同理，要將2->3->4->5->6->7->8逆序艘希，就需要先把鏈表變成2->8->7->6->5->4->3硼身，然后將節(jié)點(diǎn)2鏈接到該鏈表的尾部就可以實(shí)現(xiàn)鉴未。直到鏈表只剩一個(gè)節(jié)點(diǎn)8。所以可以看出遞歸定義為：將第一個(gè)節(jié)點(diǎn)后面的子鏈表逆序鸠姨，然后對(duì)該子鏈表做同樣的操作铜秆。遞歸終止的條件為：遞歸下去，直到鏈表只剩一個(gè)元素為止讶迁。下面通過代碼實(shí)現(xiàn):

def RecursiveReverese(head):
    '''
    沒有頭節(jié)點(diǎn)
    '''
    #Recursive：遞歸  Reverese：逆序
    #先判斷鏈表是否只有一個(gè)元素连茧，是則返回上一層；是否為空巍糯，是則返回
    if head is None or head.next is None:
        return head
    else:
        #不為空啸驯，則遞歸逆序除第一個(gè)節(jié)點(diǎn)外的子鏈表
        newhead = RecursiveReverese(head.next)
        #前面當(dāng)鏈表只有一個(gè)元素時(shí)返回了上一層，也就是說此時(shí)有兩個(gè)元素祟峦。
        #將當(dāng)前遍歷到的節(jié)點(diǎn)鏈接到鏈表尾部
        head.next.next = head
        head.next = None
    return newhead

def Reverese(head):
    '''
    帶頭節(jié)點(diǎn)
    :param head: 帶頭節(jié)點(diǎn)鏈表
    :return: 逆序后的鏈表
    '''
    if head.next is None:
        return head
    #因?yàn)轭^節(jié)點(diǎn)沒有數(shù)據(jù)罚斗，不需要參與逆序，所以從第一個(gè)節(jié)點(diǎn)開始逆序
    newhead=RecursiveReverese(head.next)
    head.next=newhead
    return head

處理函數(shù)就是這些宅楞，下面給個(gè)全部的代碼：

#先建立節(jié)點(diǎn)對(duì)象LNode
class LNode:
    def __init__(self,arg):
        # 這是數(shù)據(jù)域data
        self.data = arg    
        # 這是節(jié)點(diǎn)的next域针姿，也就是下一個(gè)節(jié)點(diǎn)的引用
        self.next = None  
"""
方法功能：創(chuàng)建一個(gè)帶頭節(jié)點(diǎn)的單鏈表
"""
def creatLink(x):
    #  x是鏈表的長(zhǎng)度 
    i = 1
    head = LNode(None) # 先構(gòu)造單鏈表的頭節(jié)點(diǎn)
    tmp = None # 用來指向新添加的節(jié)點(diǎn)
    cur = head # 用來指向鏈表的最后一個(gè)節(jié)點(diǎn)
    while i <= x:
        tmp = LNode(i)
        cur.next = tmp
        cur = tmp
        i += 1
    return head
def RecursiveReverese(head):
    '''
    沒有頭節(jié)點(diǎn)
    '''
    #Recursive：遞歸  Reverese：逆序
    #先判斷鏈表是否只有一個(gè)元素，是則返回上一層厌衙；是否為空距淫，是則返回
    if head is None or head.next is None:
        return head
    else:
        #不為空，則遞歸逆序除第一個(gè)節(jié)點(diǎn)外的子鏈表
        newhead = RecursiveReverese(head.next)
        #前面當(dāng)鏈表只有一個(gè)元素時(shí)返回了上一層婶希，也就是說此時(shí)有兩個(gè)元素榕暇。
        #將當(dāng)前遍歷到的節(jié)點(diǎn)鏈接到鏈表尾部
        head.next.next = head
        head.next = None
    return newhead

def Reverese(head):
    '''
    帶頭節(jié)點(diǎn)
    :param head: 帶頭節(jié)點(diǎn)鏈表
    :return: 逆序后的鏈表
    '''
    if head.next is None:
        return head
    #因?yàn)轭^節(jié)點(diǎn)沒有數(shù)據(jù)，不需要參與逆序喻杈，所以從第一個(gè)節(jié)點(diǎn)開始逆序
    newhead=RecursiveReverese(head.next)
    head.next=newhead
    return head

if __name__=='__main__':
    head = creatLink(8)
    cur = head.next
    #打印鏈表
    print("BeforeReversehead:")
    while cur is not None:
        print(cur.data)
        cur = cur.next
    #調(diào)用逆序函數(shù)
    head = Reverese(head)
    cur = head.next
    #打印逆序后鏈表
    print("AfterRevershead:")
    while cur is not None:
        print(cur.data)
        cur = cur.next

運(yùn)行結(jié)果如下：

程序運(yùn)行結(jié)果

大家自己寫一寫彤枢，學(xué)習(xí)效果更好喲！在我的github上也有代碼筒饰，你可以對(duì)照一下缴啡，亦可以將你的代碼發(fā)我給我、私信我龄砰，也可以關(guān)注我自己的公眾號(hào)：DKider 來聯(lián)系我盟猖，我們一起看看對(duì)不對(duì)，一起學(xué)習(xí)一起進(jìn)步换棚。

加油Ｊ礁洹！固蚤！