Program JavaScript untuk mencari panjang gelung dalam senarai terpaut

Dalam program ini kita akan mendapat senarai terpaut yang mungkin mengandungi gelung dan kita perlu mengetahui sama ada gelung itu wujud dan kemudian apakah saiz gelung itu. Marilah kita menggunakan kaedah yang sangat terkenal untuk mencari panjang gelung dengan bantuan kod dan membincangkan kerumitan masa dan ruangnya.

Pengenalan kepada masalah

Dalam soalan ini, seperti yang kita lihat di atas, kita diberikan senarai terpaut yang mungkin mengandungi gelung atau tidak, jika gelung itu wujud, kita perlu mencari panjang gelung, jika tidak, kita perlu mengembalikan sifar, kerana terdapat tidak Ada kitaran. Kami akan menggunakan kaedah gelung Floyd untuk mencari gelung dan kemudian menyemak saiznya. Contohnya, jika kita diberi senarai pautan -

List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

Ada kitaran dari nod yang mengandungi 8 kepada nod yang mengandungi 4, bermakna 8 disambungkan dengan 4, membentuk kitaran yang panjangnya 5, kita perlu mengesannya.

Kaedah

Dalam soalan ini, kita akan menggunakan kaedah gelung Floyd untuk mengesan gelung dan kemudian kita akan menggunakan konsep carian panjang untuk mencari panjang gelung. Mari kita lihat langkah asas masalah dahulu, dan kemudian kita akan beralih kepada kaedah Freudian dan kaedah panjang.

• Pertama, kami akan mencipta kelas untuk menyediakan struktur asas nod senarai terpaut dan mentakrifkan pembina di dalamnya untuk memulakan nilai nod.

• Kemudian kami mencipta fungsi untuk menolak elemen ke dalam senarai terpaut yang diberikan.

• Kami membuat senarai terpaut menggunakan kaedah di atas dan kemudian memautkan nod terakhir ke nod lain untuk membentuk gelung di dalamnya.

Algoritma Freud

Dalam algoritma ini, kami melintasi senarai terpaut Setelah kami memasuki senarai terpaut, kami tidak boleh keluar dari mana-mana nod. Ini bermakna jika kita mempunyai dua penunjuk dalam bahagian bulat senarai terpaut dan satu penuding menggerakkan satu nod pada satu masa dan satu lagi menggerakkan dua nod pada satu masa, ia akan bertemu pada satu ketika.

• Selepas melaksanakan algoritma, kami akan memanggil fungsi dan menyemak sama ada gelung itu wujud

• Jika ada gelung, kita akan panggil fungsi anter untuk mencari panjang gelung.

• Sebaliknya, kami akan kembali dan mencetak bahawa gelung itu tidak wujud.

Contoh

Dalam contoh di bawah, kami mentakrifkan senarai terpaut dan menambah 8 nod padanya. Kami membentuk gelung dalam senarai terpaut dengan menyambungkan nod 8 ke nod 4. Oleh itu, ia membentuk gelung lima nod.

// class to provide the structure to the linked list node
class Node{
   constructor(data) {
      this.value = data
      this.next = null;
   }
}
// function to add values in a linked list
function push(data, head) {
   var new_node = new Node(data);
   if(head == null) {
      head = new_node;
      return head;
   }
   var temp = head
   while(temp.next != null) {
      temp = temp.next;
   }
   temp.next = new_node;
   return head;
}
// function to find the length in the loop 
function length(loop_node) {
   var count = 1;
   var temp = loop_node;
   while(temp.next != loop_node) {
      count++;
      temp = temp.next;
   }
   console.log("The length of the loop in the given linked list is: " + count);
}
// function to find the cycle in the given list 
// if the cycle is found then call the length function 
function find_node(head) {
   var slow_ptr = head;
   var fast_ptr = head;
   while(slow_ptr != null && fast_ptr != null && fast_ptr.next != null) {
      slow_ptr = slow_ptr.next;
      fast_ptr = fast_ptr.next.next;
      if(slow_ptr == fast_ptr) {
         length(slow_ptr);
         return;
      }
   }
   console.log("There is no loop present in the given linked list");
}

var head = null;

head = push(1,head)
head = push(2,head)
head = push(3,head)
head = push(4,head)
head = push(5,head)
head = push(6,head)
head = push(7,head)
head = push(8,head)

// making loop in a linked list by connecting 8 to four 
var temp = head;
while(temp.value != 4){
   temp = temp.next;
}
var temp2 = head;
while(temp2.next != null){
   temp2 = temp2.next
}
temp2.next = temp
// finding the length of the loop 
find_node(head)

Kerumitan masa dan ruang

Dalam kod di atas, kami hanya melintasi senarai pautan lengkap sekali dan bahagian gelung dilalui sehingga tiga kali, yang menjadikan kerumitan masa menjadi linear. Jadi kerumitan masa kod di atas adalah linear, iaitu O(N), dengan N ialah saiz senarai terpaut.

Memandangkan kami tidak menggunakan sebarang ruang tambahan, kerumitan masa program ialah O(1).

Kesimpulan

Dalam tutorial ini, kami mempelajari cara mencari panjang gelung hadir dalam senarai terpaut dengan melaksanakan konsep dalam bahasa JavaScript. Kami menggunakan algoritma pencarian gelung Floyd untuk mencari gelung dalam senarai terpaut yang diberikan, dan kemudian kami menggunakan gelung sementara untuk melelaran melalui gelung dan mencari panjangnya. Kerumitan masa kod di atas ialah O(N) dan kerumitan ruang ialah O(1).

Atas ialah kandungan terperinci Program JavaScript untuk mencari panjang gelung dalam senarai terpaut. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!