溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
如何把一個單鏈表進行反轉？
方法1：將單鏈表儲存為數組，然后按照數組的索引逆序進行反轉。
方法2：使用3個指針遍歷單鏈表，逐個鏈接點進行反轉。
方法3：從第2個節點到第N個節點，依次逐節點插入到第1個節點(head節點)之后，最后將第一個節點挪到新表的表尾。
方法4: 遞歸(相信我們都熟悉的一點是，對于樹的大部分問題，基本可以考慮用遞歸來解決。但是我們不太熟悉的一點是，對于單鏈表的一些問題，也可以使用遞歸。可以認為單鏈表是一顆永遠只有左(右)子樹的樹，因此可以考慮用遞歸來解決。或者說，因為單鏈表本身的結構也有自相似的特點，所以可以考慮用遞歸來解決)
開辟輔助數組，新建表頭反轉，就地反轉，遞歸反轉
# -*- coding: utf-8 -*-
'''
鏈表逆序
'''
class ListNode:
def __init__(self,x):
self.val=x
self.next=None
'''
第一種方法：
對于一個長度為n的單鏈表head,用一個大小為n的數組arr儲存從單鏈表從頭
到尾遍歷的所有元素，在從arr尾到頭讀取元素簡歷一個新的單鏈表
時間消耗O(n),空間消耗O(n)
'''
def reverse_linkedlist1(head):
if head == None or head.next == None: #邊界條件
return head
arr = [] # 空間消耗為n,n為單鏈表的長度
while head:
arr.append(head.val)
head = head.next
newhead = ListNode(0)
tmp = newhead
for i in arr[::-1]:
tmp.next = ListNode(i)
tmp = tmp.next
return newhead.next
'''
開始以單鏈表的第一個元素為循環變量cur,并設置2個輔助變量tmp,保存數據;
newhead,新的翻轉鏈表的表頭。
時間消耗O(n),空間消耗O(1)
'''
def reverse_linkedlist2(head):
if head == None or head.next == None: #邊界條件
return head
cur = head #循環變量
tmp = None #保存數據的臨時變量
newhead = None #新的翻轉單鏈表的表頭
while cur:
tmp = cur.next
cur.next = newhead
newhead = cur # 更新 新鏈表的表頭
cur = tmp
return newhead
'''
開始以單鏈表的第二個元素為循環變量，用2個變量循環向后操作,并設置1個輔助變量tmp,保存數據;
時間消耗O(n),空間消耗O(1)
'''
def reverse_linkedlist3(head):
if head == None or head.next == None: #邊界條件
return head
p1 = head #循環變量1
p2 = head.next #循環變量2
tmp = None #保存數據的臨時變量
while p2:
tmp = p2.next
p2.next = p1
p1 = p2
p2 = tmp
head.next = None
return p1
'''
遞歸操作，先將從第一個點開始翻轉轉換從下一個節點開始翻轉
直至只剩一個節點
時間消耗O(n),空間消耗O(1)
'''
def reverse_linkedlist4(head):
if head is None or head.next is None:
return head
else:
newhead=reverse_linkedlist4(head.next)
head.next.next=head
head.next=None
return newhead
def create_ll(arr):
pre = ListNode(0)
tmp = pre
for i in arr:
tmp.next = ListNode(i)
tmp = tmp.next
return pre.next
def print_ll(head):
tmp = head
while tmp:
print tmp.val
tmp=tmp.next
a = create_ll(range(5))
print_ll(a) # 0 1 2 3 4
a = reverse_linkedlist1(a)
print_ll(a) # 4 3 2 1 0
a = reverse_linkedlist2(a)
print_ll(a) # 0 1 2 3 4
a = reverse_linkedlist3(a)
print_ll(a) # 4 3 2 1 0
a = reverse_linkedlist4(a)
print_ll(a) # 0 1 2 3 4
到此這篇關于用python介紹4種常用的單鏈表翻轉的方法小結的文章就介紹到這了,更多相關python 單鏈表翻轉內容請搜索億速云以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持億速云！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
