© BEST-BACKGROUNDS/Shutterstock.com
鍊錶有很多應用,例如音樂和圖像處理以及表示圖形、樹和更複雜的數據結構。但是為什麼要反轉鍊錶呢?讓我們開始吧。
什麼是反向鍊錶?
正如您可能猜到的那樣,它是一個鍊錶……被反向了!通常,每個節點指向列表中的下一個節點,從頭節點開始到尾節點結束。但是,當你反轉一個鍊錶時,指針也會反轉,所以頭變成了尾,尾變成了頭。考慮 5 節點列表的簡單情況。這通常看起來像這樣:
head → node1 → node2 → node3 → node4 → node5 → tail
一旦我們反轉列表,我們得到:
tail → node5 → node4 → node3 → node2 → node1 → head
即使列表變長,涉及到的數據值變多,原理還是一樣。
Why Would You Want to Reverse a Linked List?
由於反向鍊錶仍然是鍊錶,所以在本質上,很多應用都是類似的。因此,反向列表仍然用於在堆棧和隊列中實現更多的數據結構。但是,反向鍊錶給錶帶來了一些獨特的用途:
由於元素是反向的,我們可以打印元素並以相反的順序處理列表。如果您想顯示瀏覽器的互聯網歷史記錄,這將很有幫助。如果您想刪除列表末尾附近的一些元素,反轉它會使這變得容易得多。這是因為這些元素現在位於列表的開頭。這可以節省很多時間,尤其是在列表很大的時候。反轉列表就不需要遍歷整個列表。有時候,我們想對整個列表進行遞歸算法,在每個節點上執行操作。在其中一些情況下,以相反的順序處理它們可能更有意義。使用反向鍊錶的另一個原因是檢查列表是否為回文——這意味著序列向前或向後是相同的。這方面的一個例子是數字 212。無論您如何看待它,數據值的序列都是相同的。
如何反轉鍊錶
通常有兩種反轉鍊錶的方法——迭代方法和遞歸方法。讓我們來看看這些。
迭代方法
在這種方法中,我們重複執行算法,直到每個指針都被反轉。我們通過使用“prev”、“curr”和“next”屬性跟踪我們的節點來做到這一點。我們可以這樣分配它們:
while (current !=NULL) { next=current-> next current-> next=prev prev=current current=next } head_ref=prev
基本上是“while”語句遍歷每個不為空的節點。
下一行跟踪列表中的下一個節點,因此一旦我們反轉指針,我們就不會丟失它。
然後,我們將當前節點的“next”屬性設置為前一個節點,反轉指針。
下一行將“prev”屬性設置為前一個節點,像我們一樣跟踪它
倒數第二行表示“當前”指針在下一個節點上,因此我們可以沿著列表迭代移動。
最後,我們設置“head_ref ” 指向原始列表的最後一個節點,這將是反向列表中的第一個節點。因此,我們將其設置為新的頭節點。
以下是我們如何在 Python 中實現此過程:
class Node: def __init__(self, data): self.data=data self. next=None 類 LinkedList: def __init__(self): self.head=None def push(self, new_data): new_node=Node(new_data) new_node.next=self.head self.head=new_node def reverse(self): prev_node=None current_node=self.head while current_node is not None: next_node=current_node.next current_node.next=prev_node prev_node=current_node current_node=next_node self.head=prev_node def printList(self): current_node=self.head while current_node: print( current_node.data, end=””) current_node=current_node.next my_list=LinkedList() my_list.push(16) my_list.push(2) my_list.push(19) my_list.push(71) print(“給定鍊錶”) my_list.printList() my_list.reverse () print(“\nReversed linked list”) my_list.printList()
首先,我們定義類“Node”和“LinkedList”。然後,我們定義了“push”函數,用於將新節點添加到列表的開頭,指定為頭節點。
然後,我們看到實現的“reverse”函數
最後,我們為“LinkedList”類定義了“printList”函數,它打印每個節點的數據值,一直持續到“current_node” ”等於“無”,表明我們已經到達列表的末尾。請參閱屏幕截圖以了解其在 Python 中的工作原理。
反轉鍊錶的迭代方法,用 Python 實現。
©”TNGD”.com
遞歸方法
另一種反轉方法鍊錶是遞歸方法。迭代方法通過使用循環或重複指令來解決問題,而遞歸方法在同一問題的越來越小的示例上執行相同的功能。一旦這些子問題得到解決,這些解決方案就會組合起來,給出初始問題的總體結果。讓我們看看遞歸如何反轉鍊錶:
首先,我們將鍊錶分成兩部分,第一個節點和剩餘鍊錶。
然後,我們稱“
然後將這個反向列錶鍊接到第一個節點,並將原始頭指針設置為 NULL。新的頭指針被設置為新的頭節點,並且列表被反轉。
下面看看它是如何實現的:
class Node: def__init__(self, data): self. data=data self.next=None class LinkedList: def__init__(self): self.head=None def push(self, new_data): new_node=Node(new_data) new_node.next=self.head self.head=new_node def reverse_recursive( self, current_node): 如果 current_node 為 None 或 current_node.next 為 None: 返回 current_node rest=self.reverse_recursive(current_node.next) current_node.next.next=current_node current_node.next=None return rest def reverse(self): self. head=self.reverse_recursive(self.head) def printList(self): current_node=self.head while current_node: print(current_node.data, end=””) current_node=current_node.next print() my_list=LinkedList() my_list.推送(16) my_list.push(2) my_list.push(19) 我的_list.push(71) print(“給定鍊錶”) my_list.printList() my_list.reverse() print(“反向鍊錶(遞歸):”) my_list.printList()
很多這段代碼是與迭代過程相同。不出所料,主要區別在於使用的反向函數。
在這種情況下,我們將函數“reverse_recursive”定義為當前節點的函數。通過以下一個節點作為輸入調用反向函數遞歸地反轉此後的每個節點,直到當前節點等於“無”。這發生在到達列表末尾時,或者在列表中只有一個節點的簡單情況下。
然後,通過更新下一個節點的“next”屬性來反轉當前節點到當前節點,當前節點的“下一個”屬性為“無”。當前節點成為反轉列表的尾部。
反向鍊錶的遞歸方法,用 Python 實現。
©”TNGD”.com
總結
當你需要反向時鍊錶,您可以在迭代方法和遞歸方法之間進行選擇。迭代方法依賴於在每個節點的“while”循環中重複相同的指令,而遞歸函數在相同問題的較小實例上執行它們的函數。反轉鍊錶可用於檢測列表的回文性和修改原始列表末尾的元素。
如何反轉鍊錶,帶示例常見問題解答(常見問題解答)
什麼是反向鍊錶?
反向鍊錶是其元素順序顛倒的鍊錶,因此最後一個節點成為第一個新列表的節點,並且指針被反轉。
為什麼要反轉鍊錶?
反轉列表可以用於確定列表是否回文,修改原始列表末尾的元素(因為它們現在位於開頭),或者當您想要使用某些更適合與反向列表一起使用的算法時。
如何反轉鍊錶?
反轉鍊錶的最常見方法是通過迭代或遞歸函數。迭代方法通過遍歷列表並更改每個節點的指針來工作,而遞歸反向函數通過從頭節點反轉列表然後更新當前節點的指針來工作。
如何你反轉雙向鍊錶和循環鍊錶嗎?
你可以反轉雙向鍊錶,就像反轉單鍊錶一樣,但是你需要更新“next”和每個節點的“prev”屬性相應。對於循環鍊錶,需要更新尾節點的“next”屬性指向新的頭節點。
反轉鍊錶的時間複雜度是多少?
時間複雜度等於O(n),其中n是節點數,因為不管用什麼方法都要遍歷鍊錶來反轉指針。
反轉鍊錶的空間複雜度是多少?
對於迭代方法,空間複雜度等於 O(1),因為反轉列表所需的臨時變量仍然存在持續的。對於遞歸方法,空間複雜度等於 O(n),因為您必須將遞歸函數的每次調用存儲在堆棧中。