Programme JavaScript pour vérifier si une liste chaînée unique est un palindrome

Une liste chaînée unidirectionnelle est une structure de données linéaire qui est stockée en mémoire de manière discontinue, chaque bloc étant connecté en contenant l'adresse du bloc suivant (également appelé nœud). Un palindrome peut être interprété comme un ensemble de caractères, de chiffres, etc., et se lit de la même manière du recto et du verso. Nous obtiendrons une liste à chaînage unique et devrons déterminer si la valeur stockée par le nœud est égale à l'avant et à l'arrière.

Entrez

1 -> 2 -> 3 -> 3 -> 2 -> 1 -> null

Sortie

Yes, the given linked list is a palindrome. 

Instructions

Nous pouvons voir que le premier et le dernier nœud ont la même valeur, l'avant-dernier nœud ont la même valeur, et ainsi de suite, chaque nœud qui est à la même distance de l'avant et de l'arrière a la même valeur.

Entrez

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

Sortie

No, the given linked list is not a palindrome. 

Instructions

Ici, les premier et deuxième nœuds sont respectivement égaux au dernier et à l'avant-dernier nœuds, mais les nœuds suivants n'ont pas la même valeur.

Utilisez la pile

Dans cette méthode, nous créons d'abord une liste chaînée à l'aide de cette classe, puis définissons quelques fonctions de base pour ajouter des données à la liste chaînée et imprimer les données présentes dans la liste chaînée.

Exemple

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   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){
   return tail.next = new Node(data);
}

// function to find the string is palindrome or not
function check(head){
   var temp = head;
   var stack = []; // defining the stack    
   while(temp != null){
      stack.push(temp.value);
      temp = temp.next;
   }    
   temp = head;
   while(temp != null){
      if(temp.value != stack.pop()){
         return false;
      }
      temp = temp.next;
   }
   return true;
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(3,head, tail)
tail = add(2,head, tail)
tail = add(1,head, tail)
console.log("The given linked list is: ")
print(head)

// calling function to check if the current linked list is a palindrome or not 
if(check(head)){
   console.log("Yes, the given linked list is a palindrome");
}
else{
   console.log("No, the given linked list is not a palindrome");
}

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N), où N est la longueur de la liste chaînée.

La complexité spatiale du code ci-dessus est O(N) car nous utilisons une structure de données de pile pour y stocker les éléments.

Utiliser la récursion

Dans cette méthode, nous trouvons d'abord la longueur de la liste chaînée donnée, puis nous parcourons jusqu'au milieu de la liste chaînée en utilisant la récursivité. Si la longueur de la liste chaînée donnée est impaire, nous renverrons le nœud suivant au nœud du milieu, sinon nous renverrons le nœud du milieu, et pour chaque appel, nous obtiendrons le nœud correspondant par derrière à partir de l'appel récursif.

Exemple

// class to create the structure of the nodes 
class Node{
   constructor(data){
      this.value = data;
      this.next = null;
   }
}

// function to print the linked list
function print(head){
   var temp = head;
   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){
   return tail.next = new Node(data);
}

// recursive function 
function recursion(head, number, odd){
   if(number == 0){
      if(odd){
         return head.next;
      }
      else{
         return head;
      }
   }
   var temp = recursion(head.next, number-1, odd);
   
   // if the current value is not equal then don't move to the next node
   
   // by this we will not reach null in the end 
   
   // indicated the not palindrome 
   
   if(temp.value != head.value){
      return temp;
   }
   else{
      return temp.next;
   }
}

// function to check if the given linked list is palindrome or not 
function check(head){
   var temp = head;
   var len = 0;

   // finding the length of the given linked list 
   while(temp != null){
      len++;
      temp = temp.next;
   }

   // calling the recursion function 
   if(recursion(head, Math.floor(len/2), len & 1) == null){
      return true;
   }
   else{
      return false;
   }
}

// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(3,head, tail)
tail = add(2,head, tail)
tail = add(1,head, tail)
console.log("The given linked list is: ")
print(head)

// calling function to check if the current linked list is a palindrome or not 
if(check(head)){
   console.log("Yes, the given linked list is a palindrome");
}
else{
   console.log("No, the given linked list is not a palindrome");
}

Conclusion

Dans ce tutoriel, nous avons implémenté un programme JavaScript pour vérifier si un nœud de liste chaînée donné contient une valeur dans un palindrome. Nous avons implémenté deux codes utilisant la pile et la récursion. La complexité temporelle de la pile est O(N) et la complexité spatiale est O(N). La complexité spatiale de la méthode récursive est O(1) (uniquement lorsque les données d'appel récursives sont). ne pas considérer).

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!