python遞歸&迭代方法實現鏈表反轉
定義鏈表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))
到此這篇關於python遞歸&迭代方法實現鏈表反轉的文章就介紹到這瞭,更多相關python鏈表反轉內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！