資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式獲取單次迭代連結串列的中間元素
連結串列用於儲存非連續記憶體位置中的資料。包含資料項的節點使用指標連結。每個節點包含兩個欄位。第一個欄位用於儲存資料，第二個欄位包含指向下一個節點的連結。
暴力破解技術
為了找到連結串列的中間元素，暴力破解技術是透過迭代整個連結串列直到遇到 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
更新於: 2023年4月24日
1K+ 瀏覽量
廣告