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.
1 -> 2 -> 3 -> 3 -> 2 -> 1 -> null
Yes, the given linked list is a palindrome.
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.
1 -> 2 -> 3 -> 4 -> 2 -> 1 -> null
No, the given linked list is not a palindrome.
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.
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.
// 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");
}
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.
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.
// 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");
}
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!
outils de développement Python
Comment configurer un nom de domaine automatiquement redirigé
niveau d'isolement des transactions MySQL
La différence entre tas et pile
Utilisation de la commande zip de compression Linux
que sont les nombres premiers
Supprimer les informations exif
La fonction de la commande net user
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
