Eine einseitig verknüpfte Liste ist eine lineare Datenstruktur, die diskontinuierlich im Speicher gespeichert wird, wobei jeder Block durch die Speicherung der Adresse des nächsten Blocks (auch Knoten genannt) verbunden ist. Ein Palindrom kann als eine Reihe von Zeichen, Zahlen usw. interpretiert werden und liest sich von vorne und hinten gleich. Wir erhalten eine einfach verknüpfte Liste und müssen herausfinden, ob der vom Knoten gespeicherte Wert vorne und hinten gleich ist.
1 -> 2 -> 3 -> 3 -> 2 -> 1 -> null
Yes, the given linked list is a palindrome.
Wir können sehen, dass der erste und der letzte Knoten den gleichen Wert haben, der vorletzte und der vorletzte Knoten den gleichen Wert haben usw. Jeder Knoten, der von vorne und hinten den gleichen Abstand hat, hat den gleichen Wert.
1 -> 2 -> 3 -> 4 -> 2 -> 1 -> null
No, the given linked list is not a palindrome.
Hier sind der erste und der zweite Knoten gleich dem letzten bzw. vorletzten Knoten, aber die Knoten danach haben nicht den gleichen Wert.
Bei dieser Methode erstellen wir zunächst eine verknüpfte Liste mit dieser Klasse und definieren dann einige Grundfunktionen, um Daten zur verknüpften Liste hinzuzufügen und die in der verknüpften Liste vorhandenen Daten zu drucken.
// 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");
}
Die zeitliche Komplexität des obigen Codes beträgt O(N), wobei N die Länge der verknüpften Liste ist.
Die räumliche Komplexität des obigen Codes beträgt O(N), da wir eine Stapeldatenstruktur verwenden, um die darin enthaltenen Elemente zu speichern.
Bei dieser Methode ermitteln wir zunächst die Länge der angegebenen verknüpften Liste und gehen dann mithilfe der Rekursion zur Mitte der verknüpften Liste. Wenn die Länge der angegebenen verknüpften Liste ungerade ist, geben wir den nächsten zum mittleren Knoten zurück, andernfalls geben wir den mittleren Knoten zurück und für jeden Aufruf erhalten wir den entsprechenden Knoten von hinten aus dem rekursiven Aufruf.
// 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");
}
In diesem Tutorial haben wir ein JavaScript-Programm implementiert, um zu überprüfen, ob ein bestimmter verknüpfter Listenknoten einen Wert in einem Palindrom enthält. Wir haben zwei Codes mithilfe von Stack und Rekursion implementiert. Die zeitliche Komplexität des Stacks beträgt O(N) und die räumliche Komplexität der rekursiven Methode beträgt O(1) (nur wenn die rekursiven Aufrufdaten vorhanden sind). nicht berücksichtigen).
Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Überprüfen, ob eine einfach verknüpfte Liste ein Palindrom ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
