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+ 瀏覽量

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告