Python-Programm zum Abrufen des mittleren Elements einer verknüpften Liste, abgeschlossen in einer einzigen Iteration

Verknüpfte Listen werden verwendet, um Daten an nicht zusammenhängenden Speicherorten zu speichern. Knoten, die Datenelemente enthalten, werden mithilfe von Zeigern verknüpft. Jeder Knoten besteht aus zwei Feldern. Das erste Feld dient zur Speicherung der Daten und das zweite Feld enthält den Link zum nächsten Knoten.

Brute-Force-Cracking-Technologie

Um das mittlere Element einer verknüpften Liste zu finden, besteht die Brute-Force-Technik darin, die Länge der verknüpften Liste zu ermitteln, indem die gesamte verknüpfte Liste durchlaufen wird, bis NULL gefunden wird, und dann die Länge durch 2 geteilt wird, um das mittlere Element der verknüpften Liste zu erhalten Index der Liste. Nachdem Sie den Index des Zwischenelements erhalten haben, iterieren Sie die verknüpfte Liste erneut von Anfang an und stoppen Sie, wenn der erforderliche Index erreicht ist. Das Datenelement an diesem Index gibt das Zwischenelement an.

• Nehmen Sie eine Variable namens „temp“, die auf HEAD zeigt, und initialisieren Sie „len“ auf 0

• Verwenden Sie temp, um die verknüpfte Liste zu durchlaufen, bis NULL erreicht ist, und fügen Sie an jedem Knoten 1 zu „len“ hinzu.

• Nachdem Sie die Länge der verknüpften Liste ermittelt haben, initialisieren Sie temp erneut auf HEAD. Durchlaufen Sie die verknüpfte Liste bis len//2.

Verwenden Sie langsame und schnelle Zeiger (einzelne Iteration)

Wir werden zwei Zeiger verwenden, um die verknüpfte Liste zu durchlaufen. Einer wird als „langsamer Zeiger“ und der andere als „schneller Zeiger“ bezeichnet.

Der schnelle Zeiger bewegt sich doppelt so schnell wie der langsame Zeiger.

Wenn der schnelle Zeiger das Ende der verknüpften Liste erreicht, befindet sich der langsame Zeiger am mittleren Knoten.

Daher können wir den Inhalt der Zwischenknoten direkt drucken.

Beispiel

Beachten Sie die Liste der Links unten. Das mittlere Element ist 3.

Der schnelle Zeiger hat den letzten Knoten in der verknüpften Liste erreicht und der langsame Zeiger zeigt jetzt auf Knoten 3. Daher ist 3 das mittlere Element der angegebenen verknüpften Liste. Betrachten Sie nun 6 Knoten.

Beispiel

Der schnelle Zeiger hat NULL erreicht und der langsame Zeiger zeigt auf den 4. Knoten. Daher ist das mittlere Element 4.

Algorithmus

• Stellen Sie sicher, dass „langsam“ und „schnell“ auf den KOPF der verknüpften Liste zeigen.

• Erhöhen Sie den schnellen Zeiger um 2 und den langsamen Zeiger um 1, bis der schnelle Zeiger und fast.next nicht gleich NULL sind

• Drucken Sie den Wert am langsamen Zeiger.

• Die Zeitkomplexität ist 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()

Ausgabe

The linked list elements are: 1 2 3 4 5 

the middle element is  3

Das obige ist der detaillierte Inhalt vonPython-Programm zum Abrufen des mittleren Elements einer verknüpften Liste, abgeschlossen in einer einzigen Iteration. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!