JavaScript-Programm zum Überprüfen, ob eine einfach verknüpfte Liste ein Palindrom ist

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.

Eintreten

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

Ausgabe

Yes, the given linked list is a palindrome. 

Anleitung

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.

Eintreten

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

Ausgabe

No, the given linked list is not a palindrome. 

Anleitung

Hier sind der erste und der zweite Knoten gleich dem letzten bzw. vorletzten Knoten, aber die Knoten danach haben nicht den gleichen Wert.

Verwenden Sie den Stapel

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.

Beispiel

// 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");
}

Zeitliche und räumliche Komplexität

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.

Rekursion verwenden

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.

Beispiel

// 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");
}

Fazit

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!