Program Python untuk mendapatkan elemen tengah senarai terpaut, diselesaikan dalam satu lelaran

Senarai terpaut digunakan untuk menyimpan data di lokasi memori yang tidak bersebelahan. Nod yang mengandungi item data dipautkan menggunakan penunjuk. Setiap nod terdiri daripada dua medan. Medan pertama digunakan untuk menyimpan data dan medan kedua mengandungi pautan ke nod seterusnya.

Teknologi keretakan brute force

Untuk mencari elemen tengah senarai terpaut, teknik brute force ialah mencari panjang senarai terpaut dengan mengulangi keseluruhan senarai terpaut sehingga NULL ditemui, kemudian bahagikan panjang dengan 2 untuk mendapatkan elemen tengah daripada indeks senarai terpaut. Selepas mendapat indeks elemen perantaraan, ulang senarai terpaut sekali lagi dari awal dan berhenti apabila indeks yang diperlukan dicapai. Item data pada indeks ini memberikan elemen perantaraan.

• Ambil pembolehubah bernama "temp" menunjuk ke HEAD dan mulakan "len" kepada 0

• Lelaran ke atas senarai terpaut menggunakan temp sehingga NULL dicapai, menambah "len" sebanyak 1 pada setiap nod.

• Selepas mendapat panjang senarai terpaut, mulakan temp kepada HEAD sekali lagi. Lelaran melalui senarai terpaut sehingga len//2.

Menggunakan penunjuk perlahan dan pantas (lelaran tunggal)

Kami akan menggunakan dua penunjuk untuk melintasi senarai terpaut. Satu dipanggil "penunjuk perlahan" dan satu lagi dipanggil "penunjuk cepat".

Penunjuk pantas bergerak dua kali lebih pantas daripada penunjuk perlahan.

Apabila penuding pantas sampai ke penghujung senarai terpaut, penuding perlahan akan berada di nod tengah.

Oleh itu, kita boleh terus mencetak kandungan nod perantaraan.

Contoh

Pertimbangkan senarai pautan di bawah. Unsur tengah ialah 3.

Penunjuk pantas telah mencapai nod terakhir dalam senarai terpaut, dan penunjuk perlahan kini menghala ke nod 3. Oleh itu, 3 ialah elemen tengah senarai terpaut yang diberikan. Sekarang, pertimbangkan 6 nod.

Contoh

Penunjuk pantas telah mencapai NULL dan penunjuk perlahan menghala ke nod ke-4. Oleh itu, unsur tengah ialah 4.

Algoritma

• Buat "perlahan" dan "cepat" tuding ke KETUA senarai terpaut.

• Naikkan penunjuk cepat sebanyak 2 dan penunjuk perlahan sebanyak 1 sehingga penunjuk cepat dan fast.next tidak sama dengan NULL

• Cetak nilai pada penunjuk perlahan.

• Kerumitan masa ialah 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()

Output

The linked list elements are: 1 2 3 4 5 

the middle element is  3

Atas ialah kandungan terperinci Program Python untuk mendapatkan elemen tengah senarai terpaut, diselesaikan dalam satu lelaran. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!