鍊錶用於將資料儲存在不連續的記憶體位置。包含資料項的節點使用指標連結。每個節點由兩個字段組成。第一個欄位用於儲存數據,第二個欄位包含到下一個節點的連結。
要找到鍊錶的中間元素,暴力破解技術是透過迭代整個鍊錶直到遇到 NULL 為止來找出鍊錶的長度,然後將長度除以 2 得到鍊錶的索引中間的元素。得到中間元素的索引後,從頭開始再次迭代鍊錶,到達需要的索引時停止。此索引處的資料項給出了中間元素。
取一個名為「temp」的變數指向 HEAD 並將「len」初始化為 0
#使用 temp 迭代鍊錶,直到達到 NULL,並在每個節點上將「len」加 1。
取得鍊錶的長度後,再次將temp初始化為HEAD。迭代鍊錶直到len//2。
我們將使用兩個指標來遍歷鍊錶。一種稱為“慢指針”,另一種稱為“快指針”。
快指標的移動速度是慢指標的兩倍。
當快指標到達鍊錶末端時,慢指標將位於中間節點。
因此,我們可以直接列印中間節點的內容。
考慮下面的連結列表。中間的元素是3。
快指標已到達鍊錶中的最後一個節點,現在慢指標指向節點 3。因此,3 是給定鍊錶的中間元素。現在,考慮 6 個節點。
快指標已達到 NULL,慢指標指向第 4 個節點。因此,中間元素為 4。
使「慢」和「快」指向鍊錶的HEAD。
將快指標加 2,慢指標加 1,直到快指標和 fast.next 不等於 NULL
列印慢指標處的值。
時間複雜度為 O(n)。
class Node: def __init__(self, val): self.val = val self.next = None class LinkedList: def __init__(self): self.head = None def insert_at_the_beginning(self, newVal): newNode = Node(newVal) newNode.next = self.head self.head = newNode def print_middle_element(self): slow=self.head fast=self.head while fast is not None and fast.next is not None: slow=slow.next #slow pointer moves one node fast=fast.next.next #fast pointer moves two nodes print("\n\nthe middle element is ",slow.val) def Print_the_LL(self): temp = self.head if(temp != None): print("The linked list elements are:", end=" ") while (temp != None): print(temp.val, end=" ") temp = temp.next else: print("The list is empty.") newList = LinkedList() newList.insert_at_the_beginning(5) newList.insert_at_the_beginning(4) newList.insert_at_the_beginning(3) newList.insert_at_the_beginning(2) newList.insert_at_the_beginning(1) newList.Print_the_LL() newList.print_middle_element()
The linked list elements are: 1 2 3 4 5 the middle element is 3
以上是取得鍊錶的中間元素的Python程序,在單次迭代中完成的詳細內容。更多資訊請關注PHP中文網其他相關文章!