Programme Javascript pour supprimer les doublons de la liste chaînée triée

La liste chaînée est une structure de données linéaire On nous donne une liste chaînée triée composée d'entiers. Certains numéros peuvent être répétés ou répétés et nous devons les supprimer. Étant donné que la liste chaînée donnée est triée, nous pouvons simplement la parcourir et en utilisant une boucle while, nous pouvons en supprimer les nœuds en double. Nous mettrons en œuvre un code approprié en discutant de la complexité temporelle et spatiale pour mieux comprendre la logique.

Exemple

Given linked list is: 1-> 2 -> 2 -> 3 -> 4 -> 4 -> 4 -> 5 -> 5 -> 5-> 6-> null
Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Explication - La liste chaînée donnée est triée, ce qui facilite la recherche des éléments en double et nous pouvons les supprimer en les sautant s'ils sont égaux à la valeur précédente.

Voyons comment fonctionne le code

Méthode

Nous suivrons les étapes ci-dessous pour résoudre le problème -

• Tout d'abord, nous allons créer une classe pour fournir une structure aux nœuds de la liste chaînée.

• Deuxièmement, nous créerons des fonctions qui imprimeront la liste chaînée et ajouteront de nouveaux nœuds à la liste chaînée existante.

• Nous allons créer une fonction pour transmettre l'en-tête de la liste chaînée dont nous souhaitons supprimer les éléments en double et elle renverra l'en-tête de la nouvelle liste chaînée.

• Dans un premier temps, nous vérifierons si la liste chaînée est vide ou si sa taille est égale à 1. Dans ces cas nous rendons la tête telle quelle.

• Nous allons créer deux variables, une indiquant la tête et l'autre indiquant le prochain nœud de la tête.

• Si les valeurs du nœud actuel et du nœud suivant sont égales, alors nous déplacerons le nœud suivant vers le nœud suivant et mettrons à jour l'adresse du nœud suivant du nœud actuel.

• Sinon, on passe au nœud suivant et on déplace le nœud suivant vers son nœud suivant.

• Enfin, nous retournerons l'en-tête et imprimerons la valeur présente dedans.

Exemple

Laissons-nous implémenter les étapes indiquées dans le code pour une meilleure compréhension

// class to provide structure to linked list node
class Node{
   constructor(val){
      this.value = val
      this.next = null
   }
}
// function to print the linked list
function print(head){
   var temp = head;
   if(head == null){
      console.log("The given linked list is empty");
   } else {
      var ans = ""
      while(temp.next != null){
         ans += temp.value;
         ans += " -> "
         temp = temp.next
      }
      ans += temp.value
      ans += " -> null"
   }
   console.log(ans)
}
// function to add data in linked list 
function add(data, head, tail){
   var new_node = new Node(data);
   if(head == null){
      head = new_node
      return new_node
   } else {
      tail.next = new_node;
      return new_node
   }
}
// function to remove the duplicate numbers 
function removeDupli(head){
   // if linked list is empty 
   if(head == null){
      return head;
   }
   // if linked list is of size one 
   if(head.next == null){
      return head;
   }
   var temp = head
   var next = head.next
   while(next != null){
      if(temp.value == next.value){
         next = next.next;
         temp.next = next;
      } else {
         next = next.next;
         temp = temp.next;
      }
   }
   return head;
}
// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(4,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(5,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
console.log("The given linked list is: ")
print(head)
// calling function to remove duplicate elements 
head = removeDupli(head)
console.log("The Linked list after removal of duplicate integers is: ")
print(head)

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N), où N est le nombre total de nœuds dans la liste chaînée donnée. La complexité temporelle est linéaire car nous ne parcourons la liste chaînée qu'une seule fois.

La complexité spatiale du code ci-dessus est O(1) car nous n'utilisons aucun espace supplémentaire.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme JavaScript pour supprimer les éléments en double d'une liste chaînée triée donnée. Étant donné que la liste chaînée est triée, tous les éléments en double sont adjacents les uns aux autres et peuvent être facilement supprimés en la parcourant. La complexité temporelle du programme que nous avons implémenté 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!