Programme JavaScript pour trouver la longueur d'une boucle dans une liste chaînée

Dans ce programme, nous obtiendrons une liste chaînée pouvant contenir des boucles et nous devrons savoir si la boucle existe et ensuite quelle est sa taille. Utilisons une méthode très connue pour trouver la longueur d'une boucle à l'aide de code et discutons de sa complexité temporelle et spatiale.

Introduction au problème

Dans cette question, comme nous l'avons vu plus haut, on nous donne une liste chaînée qui peut contenir ou non une boucle, si la boucle existe il faut trouver la longueur de la boucle sinon il faut retourner zéro car il n'y a pas un cycle. Nous utiliserons la méthode des boucles Floyd pour trouver les boucles puis vérifierons leur taille. Par exemple, si on nous donne une liste chaînée -

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

Il y a un cycle du nœud contenant 8 au nœud contenant 4, cela signifie que 8 est connecté à 4, formant un cycle de longueur 5, il faut le détecter.

Méthode

Dans cette question, nous utiliserons la méthode de boucle Floyd pour détecter les boucles, puis nous utiliserons le concept de recherche de longueur pour trouver la longueur de la boucle. Examinons d'abord les étapes fondamentales du problème, puis nous passerons à la méthode freudienne et à la méthode des longueurs.

• Tout d'abord, nous allons créer une classe pour fournir la structure de base des nœuds de la liste chaînée et y définir un constructeur pour initialiser les valeurs des nœuds.

• Ensuite, nous créons une fonction pour pousser des éléments dans la liste chaînée donnée.

• Nous créons une liste chaînée en utilisant la méthode ci-dessus, puis lions le dernier nœud à un autre nœud pour former une boucle en son sein.

L'algorithme de Freud

Dans cet algorithme, nous parcourons la liste chaînée. Une fois que nous entrons dans la liste chaînée, nous ne pouvons sortir d'aucun nœud. Cela signifie que si nous avons deux pointeurs dans la partie circulaire de la liste chaînée et qu'un pointeur déplace un nœud à la fois et que l'autre déplace deux nœuds à la fois, ils se rencontreront à un moment donné.

• Après avoir implémenté l'algorithme, nous appellerons la fonction et vérifierons si la boucle existe

• S'il y a une boucle, nous appellerons la fonction anthère pour trouver la longueur de la boucle.

• Par contre, on va revenir en arrière et imprimer que la boucle n'existe pas.

Exemple

Dans l'exemple ci-dessous, nous définissons une liste chaînée et y ajoutons 8 nœuds. Nous formons une boucle dans la liste chaînée en connectant le nœud 8 au nœud 4. Il forme donc une boucle de cinq nœuds.

// 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)

Complexité temporelle et spatiale

Dans le code ci-dessus, nous ne parcourons la liste chaînée complète qu'une seule fois et la partie boucle est parcourue jusqu'à trois fois, ce qui rend la complexité temporelle linéaire. Ainsi, la complexité temporelle du code ci-dessus est linéaire, c'est-à-dire O(N), où N est la taille de la liste chaînée.

Comme nous n'utilisons aucun espace supplémentaire, la complexité temporelle du programme est O(1).

Conclusion

Dans ce tutoriel, nous avons appris comment trouver la longueur d'une boucle présente dans une liste chaînée en implémentant le concept en langage JavaScript. Nous avons utilisé l'algorithme de recherche de boucle de Floyd pour trouver une boucle dans une liste chaînée donnée, puis nous avons utilisé une boucle while pour parcourir la boucle et trouver sa longueur. La complexité temporelle du code ci-dessus est O(N) et la complexité spatiale est O(1).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!