Rumah >pembangunan bahagian belakang >Tutorial Python >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.
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.
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.
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.
Penunjuk pantas telah mencapai NULL dan penunjuk perlahan menghala ke nod ke-4. Oleh itu, unsur tengah ialah 4.
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()
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!