python中如何用遞歸與迭代方法實(shí)現(xiàn)鏈表反轉(zhuǎn)

這篇文章主要講解了“python中如何用遞歸與迭代方法實(shí)現(xiàn)鏈表反轉(zhuǎn)”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“python中如何用遞歸與迭代方法實(shí)現(xiàn)鏈表反轉(zhuǎn)”吧！

定義鏈表node結(jié)構(gòu)：

class ListNode:
 
    def __init__(self,data):
        self.data = data
        self.next = None

將L轉(zhuǎn)化為鏈表：

def make_list(L):

將L初始化為鏈表：

  head = ListNode(L[0])
    cur = head
    for i in L[1:]:
        cur.next = ListNode(i)
        cur = cur.next
    return head

遍歷鏈表：

def print_list(head):
 
    cur = head
    while cur != None:
        print(cur.data,end=' ')
        cur = cur.next

遞歸法  反轉(zhuǎn)鏈表：

def reverse_list(head):

三要素：

• 1.明確函數(shù)功能，該函數(shù)可以將鏈表反轉(zhuǎn)，并返回一個(gè)頭節(jié)點(diǎn)

• 2.結(jié)束條件：當(dāng)鏈表為空或只有一個(gè)節(jié)點(diǎn)時(shí)返回

    if head==None or head.next==None:
        return head

• 3.等價(jià)條件（縮小范圍），對(duì)于數(shù)組來(lái)講，縮小范圍是n——>n-1，對(duì)于鏈表來(lái)講則可以考慮head——

>head.next
    reverse = reverse_list(head.next)  #假設(shè)reverse是head以后的、已經(jīng)反轉(zhuǎn)過(guò)的鏈表

接下來(lái)要做的是將head節(jié)點(diǎn)接到已經(jīng)反轉(zhuǎn)過(guò)的reverse上：

    tmp = head.next
    tmp.next = head
    head.next = None
 return reverse  #返回新的列表

迭代法：

def reverse_list2(head):
    #print_list(head)
    cur = head
    pre = None
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    head = pre
    return head
 
if __name__ == '__main__':
 
    L = [3,2,7,8]
    head = make_list(L)

正序打?。?/strong>

    print('原始list：')
    print_list(head)
    print('\n')

反轉(zhuǎn)后打?。?/strong>

    revere = reverse_list(head)
    print('反轉(zhuǎn)一次的list：')
    print_list(revere)
    print('\n')

反轉(zhuǎn)2：

    print('head is')
    print_list(head)  #發(fā)現(xiàn)此時(shí)head節(jié)點(diǎn)變成了最后一個(gè)節(jié)點(diǎn)，說(shuō)明函數(shù)是對(duì)head這個(gè)實(shí)例直接作用的
    print('\n')
 
    # print('revere is')
    # print_list(revere)
    # print('\n')
 
    print('反轉(zhuǎn)兩次的list：')
    print_list(reverse_list2(revere))

感謝各位的閱讀，以上就是“python中如何用遞歸與迭代方法實(shí)現(xiàn)鏈表反轉(zhuǎn)”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)python中如何用遞歸與迭代方法實(shí)現(xiàn)鏈表反轉(zhuǎn)這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！