Die Grundstruktur einer verknüpften Liste in JavaScript kann mithilfe von Klassen in JavaScript erstellt werden und dann k?nnen Knoten zur Rotation von einer Position zur anderen verschoben werden. In diesem Artikel erfahren Sie, wie Sie eine verknüpfte Liste in der Programmiersprache JavaScript im Uhrzeigersinn drehen. Wir werden Code für ein tieferes Verst?ndnis dieser Konzepte sehen.

Bei dem gegebenen Problem erhalten wir eine verknüpfte Liste und müssen diese im Uhrzeigersinn drehen. Das bedeutet, dass wir bei jeder Bewegung das letzte Element zuerst platzieren müssen. Wenn wir k-mal rotieren müssen, müssen wir das letzte Element vor dem Kopf oder Startknoten der verknüpften Liste platzieren. Um die verknüpfte Liste zu erstellen, die wir zuvor gesehen haben, ben?tigen wir eine Klasse zum Binden von Daten und einen Zeiger auf das n?chste Element.

Verknüpfte Listenstruktur

Beispiel

Zuerst erstellen wir einen Klassenknoten, der den Wert des aktuellen Knotens und einen Zeiger auf den n?chsten Knoten speichert. Danach erstellen wir eine Push-Funktion, um die Erstellung der verknüpften Liste zu unterstützen, und schlie?lich erstellen wir eine Anzeigefunktion, um das Drucken der verknüpften Liste zu unterstützen. Schauen wir uns zuerst den Code an -

// creating the class for the linked list
class Node{
   // defining the constructor for class
   constructor(){
      this.next = null; // pointer to hold the next value 
      this.value = 0; // curent value in the linked list 
   }
}
// defining push function for linked list 
function push(head,data){
   var new_node = new Node();
   new_node.value = data;
   if(head == null){
      return new_node;
   }
   var temp = head;
   while(temp.next != null){
      temp = temp.next;
   }
   temp.next = new_node;
   return head;
}
function display(head){
   var temp = head;
   var values = 0;
   while(temp){   
      values = values + temp.value + " -> ";
      temp = temp.next;
   }
   console.log(values + "null")
}
var head = null;
for(var i = 1;i<6;i++){
   head = push(head,i);
}
display(head)

Im obigen Code haben wir eine Klasse mit dem Schlüsselwort ?class“ und einen Abschnitt mit dem Schlüsselwort ?this“ erstellt, um die Daten und den Zeiger auf den n?chsten Knoten im Klassenkonstruktor zu speichern.

Danach definieren wir eine Push-Funktion, die zwei Parameter akzeptiert. Der erste Parameter ist der Kopf der verknüpften Liste und der zweite Parameter sind die Daten des neuen Knotens, den wir der verknüpften Liste hinzufügen m?chten. In der Funktion erstellen wir den neuen Knoten und speichern den Wert darin. Wir prüfen, ob der Kopf leer ist (was bedeutet, dass wir das erste Element hinzufügen) und geben dann einfach den neuen Knoten zurück. Andernfalls gehen wir mithilfe einer Schleife zum Ende der verknüpften Liste und fügen dort den neuen Knoten hinzu.

L?sung des Problems

Nachdem wir die Klasse erstellt und die erforderlichen Grundfunktionen definiert haben, gehen wir zur Hauptfunktion über, wo wir die Funktion definieren, die die letzten k Elemente an den Anfang der verknüpften Liste verschiebt, was die Drehung der verknüpften Liste darstellt. Es gibt zwei M?glichkeiten, die letzten k Elemente zum ersten Element hinzuzufügen, was einer Rechtsdrehung der verknüpften Liste entspricht, z. B. -

Wir erhalten eine verknüpfte Liste: 1 -> 2 -> 3 -> 4 -> 5 ->null

Wir wollen die aufgelisteten Links einmal im Uhrzeigersinn drehen, damit es so aussieht -

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

?hnlich sieht die verknüpfte Liste für 3 Rotationen der verknüpften Liste so aus -

Initially Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> null
After the first rotation: 5 -> 1 -> 2 -> 3 -> 4 -> null
After the second rotation: 4 -> 5 -> 1 -> 2 -> 3 -> null
After the third rotation: 3 -> 4 -> 5 -> 1 -> 2 -> null

Wir haben zwei M?glichkeiten, das letzte Element vor der verknüpften Liste hinzuzufügen, entweder einzeln oder alle auf einmal.

Drehen Sie die verknüpfte Liste einzeln um

Beispiel

Bei dieser Methode gehen wir zum letzten Knoten und verschieben ihn dann zum vorherigen Hauptknoten und aktualisieren den Hauptknoten. Schauen wir uns zuerst den Code an -

// creating the class for linked list
class Node{
   // defining the constructor for class
   constructor(){
      this.next = null; // pointer to hold the next value 
      this.value = 0; // curent value in the linked list 
   }
}
// defining push function for linked list 
function push(head,data){
   var new_node = new Node();
   new_node.value = data;
   if(head == null){
      return new_node;
   }
   var temp = head;
   while(temp.next != null){
      temp = temp.next;
   }
   temp.next = new_node;
   return head;
}

function display(head){
   var temp = head;
   var values = 0
   while(temp){
      values =  values + temp.value + " -> ";
      temp = temp.next;
   }
   console.log(values + "null")
}
function rotate(head, k){
   while(k--){
      var temp = head;
      while(temp.next.next != null){
         temp = temp.next;
      }
      var new_head = temp.next;
      temp.next = null;
      new_head.next = head;
      head = new_head;
   }
   return head;
}
var head = null;
for(var i = 1;i<6;i++){
   head = push(head,i);
}
head = rotate(head,3);
display(head);

Im obigen Code haben wir den oben definierten Grundfunktionscode für verknüpfte Listen verwendet und einfach eine neue Funktion zum Drehen der verknüpften Liste hinzugefügt.

In der Funktion ?rotieren“ durchlaufen wir die verknüpfte Liste zun?chst k-mal mithilfe einer While-Schleife und erreichen in jeder Iteration das vorletzte Element der verknüpften Liste. Dann entfernen wir das letzte Element der verknüpften Liste aus der verknüpften Liste und platzieren es vor dem Kopf der verknüpften Liste. Schlie?lich geben wir den neuen Header zurück und zeigen die neue verknüpfte Liste mithilfe der Anzeigefunktion an.

Zeitliche und r?umliche Komplexit?t

Wir haben die verknüpfte Liste k-mal verschoben und die Gr??e der verknüpften Liste betr?gt N, sodass die Gesamtzeitkomplexit?t des Programms O(N*K) betr?gt. Darüber hinaus verbrauchen wir keinen zus?tzlichen Speicherplatz, sodass die Speicherplatzkomplexit?t des Programms O(1) betr?gt, was eine Konstante ist.

Drehen Sie die verknüpfte Liste einmal

Im vorherigen Code haben wir die Elemente einzeln hinzugefügt, was O(N*N) Zeit gedauert hat, damit wir die verknüpfte Liste besser verschieben und die Gr??e der verknüpften Liste ermitteln k?nnen. Danach durchlaufen wir die verknüpfte Liste erneut, holen uns die letzten k Elemente und fügen sie am Anfang der verknüpften Liste hinzu, wodurch die zeitliche Komplexit?t des Programms O(1) wird.

Fazit

In diesem Tutorial haben wir gelernt, wie man eine verknüpfte Liste in der Programmiersprache JavaScript im Uhrzeigersinn dreht. Wir haben den Code gesehen, um die Konzepte im Detail zu verstehen. Die Grundstruktur einer verknüpften Liste in JavaScript kann mithilfe von Klassen in JavaScript erstellt werden. Anschlie?end k?nnen Knoten zur Rotation von einer Position an eine andere verschoben werden. Die zeitliche Komplexit?t des Programms betr?gt O(N*N), was weiter auf O(N) verbessert werden kann, w?hrend die r?umliche Komplexit?t des Programms O(1) ist.

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Drehen verknüpfter Listen im Uhrzeigersinn. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!