日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

python遞歸&迭代方法實現鏈表反轉_python

作者：驚瑟 ? 更新時間： 2022-04-25 編程語言

定義鏈表node結構：

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

將L轉化為鏈表：

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
?

遞歸法 ?反轉鏈表：

def reverse_list(head):

三要素：

  • 1.明確函數功能，該函數可以將鏈表反轉，并返回一個頭節點
  • 2.結束條件：當鏈表為空或只有一個節點時返回
? ? if head==None or head.next==None:
? ? ? ? return head
  • 3.等價條件（縮小范圍），對于數組來講，縮小范圍是n——>n-1，對于鏈表來講則可以考慮head——
>head.next
? ? reverse = reverse_list(head.next) ?#假設reverse是head以后的、已經反轉過的鏈表

接下來要做的是將head節點接到已經反轉過的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)
?

正序打印：

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

反轉后打印：

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

反轉2：

? ? print('head is')
? ? print_list(head) ?#發現此時head節點變成了最后一個節點，說明函數是對head這個實例直接作用的
? ? print('\n')
?
? ? # print('revere is')
? ? # print_list(revere)
? ? # print('\n')
?
? ? print('反轉兩次的list：')
? ? print_list(reverse_list2(revere))

原文鏈接：https://blog.csdn.net/qq_34062683/article/details/121308565

欄目分類
最近更新