Programme JavaScript pour faire pivoter la liste chaînée dans le sens des aiguilles d'une montre

La structure de base d'une liste chaînée en JavaScript peut être créée à l'aide de classes en JavaScript, puis les nœuds peuvent être déplacés d'une position à une autre pour une rotation. Dans cet article, nous apprendrons comment faire pivoter une liste chaînée dans le sens des aiguilles d'une montre dans le langage de programmation JavaScript. Nous verrons du code pour une compréhension plus approfondie de ces concepts.

Dans le problème donné, on nous donne une liste chaînée et nous devons la faire pivoter dans le sens des aiguilles d'une montre. Cela signifie que nous devons mettre le dernier élément en premier à chaque mouvement, si nous devons faire une rotation k fois, alors nous devons placer le dernier élément avant la tête ou le nœud de départ de la liste chaînée. Pour créer la liste chaînée que nous avons vue précédemment, nous avons besoin d'une classe pour lier les données et d'un pointeur vers l'élément suivant.

Structure de liste chaînée

Exemple

Tout d'abord, nous allons créer un nœud de classe qui stockera la valeur du nœud actuel et un pointeur vers le nœud suivant. Après cela, nous créerons une fonction push pour aider à créer la liste chaînée, et enfin, nous créerons une fonction d'affichage pour aider à imprimer la liste chaînée. Regardons d'abord le code -

// creating the class for the linked list
class Node{
   // defining the constructor for class
   constructor(){
      this.next = null; // pointer to hold the next value 
      this.value = 0; // curent value in the linked list 
   }
}
// defining push function for linked list 
function push(head,data){
   var new_node = new Node();
   new_node.value = data;
   if(head == null){
      return new_node;
   }
   var temp = head;
   while(temp.next != null){
      temp = temp.next;
   }
   temp.next = new_node;
   return head;
}
function display(head){
   var temp = head;
   var values = 0;
   while(temp){   
      values = values + temp.value + " -> ";
      temp = temp.next;
   }
   console.log(values + "null")
}
var head = null;
for(var i = 1;i<6;i++){
   head = push(head,i);
}
display(head)

Dans le code ci-dessus, nous avons créé une classe à l'aide du mot-clé class et créé une section à l'aide du mot-clé « this » pour stocker les données et le pointeur vers le nœud suivant dans le constructeur de classe.

Après cela, nous définissons une fonction push qui prendra deux paramètres, le premier paramètre est la tête de la liste chaînée et le deuxième paramètre est les données du nouveau nœud que nous voulons ajouter à la liste chaînée. Dans la fonction, nous créons le nouveau nœud et y stockons la valeur. On vérifie si la tête est vide (ce qui veut dire qu'on va ajouter le premier élément) puis on retournera simplement le nouveau nœud, sinon à l'aide d'une boucle on ira à la fin de la liste chaînée et y ajoutera le nouveau nœud.

Solution au problème

Après avoir créé la classe et défini les fonctions de base requises, nous passerons à la fonction principale où nous définirons la fonction qui déplace les k derniers éléments vers l'avant de la liste chaînée, ce qui représente la rotation de la liste chaînée. Il existe deux façons d'ajouter les k derniers éléments au premier élément, ce qui équivaut à une rotation à droite de la liste chaînée, par exemple -

.

On nous donne une liste chaînée : 1 -> 2 -> 3 -> 4 -> 5 ->null

Nous souhaitons faire pivoter les liens répertoriés une fois dans le sens des aiguilles d'une montre pour que cela ressemble à ceci -

5 -> 1 -> 2 -> 3 -> 4 -> null

De même, pour 3 rotations de la liste chaînée, la liste chaînée ressemblera à ceci -

Initially Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> null
After the first rotation: 5 -> 1 -> 2 -> 3 -> 4 -> null
After the second rotation: 4 -> 5 -> 1 -> 2 -> 3 -> null
After the third rotation: 3 -> 4 -> 5 -> 1 -> 2 -> null

Nous avons deux façons d'ajouter le dernier élément devant la liste chaînée, soit un par un, soit tous en même temps.

Faites pivoter la liste chaînée une par une

Exemple

Dans cette méthode, nous irons au dernier nœud, puis le déplacerons vers le nœud principal précédent et mettrons à jour le nœud principal. Jetons d'abord un coup d'oeil au code -

// creating the class for linked list
class Node{
   // defining the constructor for class
   constructor(){
      this.next = null; // pointer to hold the next value 
      this.value = 0; // curent value in the linked list 
   }
}
// defining push function for linked list 
function push(head,data){
   var new_node = new Node();
   new_node.value = data;
   if(head == null){
      return new_node;
   }
   var temp = head;
   while(temp.next != null){
      temp = temp.next;
   }
   temp.next = new_node;
   return head;
}

function display(head){
   var temp = head;
   var values = 0
   while(temp){
      values =  values + temp.value + " -> ";
      temp = temp.next;
   }
   console.log(values + "null")
}
function rotate(head, k){
   while(k--){
      var temp = head;
      while(temp.next.next != null){
         temp = temp.next;
      }
      var new_head = temp.next;
      temp.next = null;
      new_head.next = head;
      head = new_head;
   }
   return head;
}
var head = null;
for(var i = 1;i<6;i++){
   head = push(head,i);
}
head = rotate(head,3);
display(head);

Dans le code ci-dessus, nous avons utilisé le code de liste chaînée de fonction de base défini ci-dessus et venons d'ajouter une nouvelle fonction pour faire pivoter la liste chaînée.

Dans la fonction rotate, on parcourt d'abord la liste chaînée k fois à l'aide d'une boucle while, et à chaque itération, on atteint l'avant-dernier élément de la liste chaînée. Ensuite, nous supprimons le dernier élément de la liste chaînée de la liste chaînée et le plaçons devant l'en-tête de la liste chaînée. Enfin, nous renvoyons le nouvel en-tête et affichons la nouvelle liste chaînée à l'aide de la fonction d'affichage.

Complexité temporelle et spatiale

Nous avons déplacé la liste chaînée k fois, et la taille de la liste chaînée est N, donc la complexité temporelle globale du programme est O(N*K). De plus, nous n’utilisons aucun espace supplémentaire, donc la complexité spatiale du programme est O(1), qui est une constante.

Faites pivoter la liste chaînée une fois

Dans le code précédent, nous avons ajouté les éléments un par un, ce qui a pris un temps O(N*N), afin que nous puissions mieux déplacer la liste chaînée et obtenir la taille de la liste chaînée. Après cela, nous parcourrons à nouveau la liste chaînée et obtiendrons les k derniers éléments et les ajouterons au début de la liste chaînée, ce qui rendra la complexité temporelle du programme O(1).

Conclusion

Dans ce tutoriel, nous avons appris à faire pivoter une liste chaînée dans le sens des aiguilles d'une montre dans le langage de programmation JavaScript. Nous avons vu le code pour comprendre les concepts en profondeur. La structure de base d'une liste chaînée en JavaScript peut être créée à l'aide de classes en JavaScript, puis les nœuds peuvent être déplacés d'une position à une autre pour une rotation. La complexité temporelle du programme est O(N*N), qui peut être encore améliorée en O(N), tandis que la complexité spatiale du programme 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!