JavaScript-Programm zum Drehen verknüpfter Listen im Uhrzeigersinn

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. p>

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!