JavaScript-Programm zum Ermitteln der Länge einer Schleife in einer verknüpften Liste

In diesem Programm erhalten wir eine verknüpfte Liste, die Schleifen enthalten kann, und wir müssen herausfinden, ob die Schleife existiert und wie groß die Schleife ist. Lassen Sie uns eine sehr bekannte Methode verwenden, um mithilfe von Code die Länge einer Schleife zu ermitteln und deren zeitliche und räumliche Komplexität zu diskutieren.

Einführung in das Problem

In dieser Frage erhalten wir, wie wir oben gesehen haben, eine verknüpfte Liste, die eine Schleife enthalten kann oder nicht. Wenn die Schleife existiert, müssen wir die Länge der Schleife ermitteln, andernfalls müssen wir Null zurückgeben, weil es keine gibt ein Zyklus. Wir werden die Floyd-Loop-Methode verwenden, um Schleifen zu finden und dann ihre Größe zu überprüfen. Wenn wir zum Beispiel eine verknüpfte Liste erhalten -

List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

Es gibt einen Zyklus vom Knoten mit 8 zum Knoten mit 4, was bedeutet, dass 8 mit 4 verbunden ist und einen Zyklus der Länge 5 bildet, den wir erkennen müssen.

Methode

In dieser Frage verwenden wir die Floyd-Schleifenmethode, um Schleifen zu erkennen, und verwenden dann das Konzept der Längensuche, um die Länge der Schleife zu ermitteln. Schauen wir uns zunächst die grundlegenden Schritte des Problems an und gehen dann zur Freudschen Methode und zur Längenmethode über.

• Zuerst erstellen wir eine Klasse, um die Grundstruktur der Knoten der verknüpften Liste bereitzustellen, und definieren darin einen Konstruktor, um die Knotenwerte zu initialisieren.

• Dann erstellen wir eine Funktion, um Elemente in die angegebene verknüpfte Liste zu verschieben.

• Wir erstellen mit der oben genannten Methode eine verknüpfte Liste und verknüpfen dann den letzten Knoten mit einem anderen Knoten, um darin eine Schleife zu bilden.

Freuds Algorithmus

In diesem Algorithmus durchlaufen wir die verknüpfte Liste. Sobald wir die verknüpfte Liste betreten, können wir keinen Knoten mehr verlassen. Das heißt, wenn wir zwei Zeiger im kreisförmigen Teil der verknüpften Liste haben und ein Zeiger jeweils einen Knoten und der andere jeweils zwei Knoten bewegt, treffen sie sich irgendwann.

• Nachdem wir den Algorithmus implementiert haben, rufen wir die Funktion auf und prüfen, ob die Schleife existiert

• Wenn es eine Schleife gibt, rufen wir die Anther-Funktion auf, um die Länge der Schleife zu ermitteln.

• Andererseits gehen wir zurück und drucken aus, dass die Schleife nicht existiert.

Beispiel

Im folgenden Beispiel definieren wir eine verknüpfte Liste und fügen ihr 8 Knoten hinzu. Wir bilden eine Schleife in der verknüpften Liste, indem wir Knoten 8 mit Knoten 4 verbinden. Daher bildet es eine Schleife aus fünf Knoten.

// class to provide the structure to the linked list node
class Node{
   constructor(data) {
      this.value = data
      this.next = null;
   }
}
// function to add values in a linked list
function push(data, head) {
   var new_node = new Node(data);
   if(head == null) {
      head = new_node;
      return head;
   }
   var temp = head
   while(temp.next != null) {
      temp = temp.next;
   }
   temp.next = new_node;
   return head;
}
// function to find the length in the loop 
function length(loop_node) {
   var count = 1;
   var temp = loop_node;
   while(temp.next != loop_node) {
      count++;
      temp = temp.next;
   }
   console.log("The length of the loop in the given linked list is: " + count);
}
// function to find the cycle in the given list 
// if the cycle is found then call the length function 
function find_node(head) {
   var slow_ptr = head;
   var fast_ptr = head;
   while(slow_ptr != null && fast_ptr != null && fast_ptr.next != null) {
      slow_ptr = slow_ptr.next;
      fast_ptr = fast_ptr.next.next;
      if(slow_ptr == fast_ptr) {
         length(slow_ptr);
         return;
      }
   }
   console.log("There is no loop present in the given linked list");
}

var head = null;

head = push(1,head)
head = push(2,head)
head = push(3,head)
head = push(4,head)
head = push(5,head)
head = push(6,head)
head = push(7,head)
head = push(8,head)

// making loop in a linked list by connecting 8 to four 
var temp = head;
while(temp.value != 4){
   temp = temp.next;
}
var temp2 = head;
while(temp2.next != null){
   temp2 = temp2.next
}
temp2.next = temp
// finding the length of the loop 
find_node(head)

Zeitliche und räumliche Komplexität

Im obigen Code durchlaufen wir die gesamte verknüpfte Liste nur einmal und den Schleifenteil bis zu dreimal, wodurch die zeitliche Komplexität linear wird. Die zeitliche Komplexität des obigen Codes ist also linear, d. h. O(N), wobei N die Größe der verknüpften Liste ist.

Da wir keinen zusätzlichen Platz verbrauchen, beträgt die zeitliche Komplexität des Programms O(1).

Fazit

In diesem Tutorial haben wir gelernt, wie man die Länge einer in einer verknüpften Liste vorhandenen Schleife ermittelt, indem man das Konzept in der JavaScript-Sprache implementiert. Wir haben Floyds Schleifensuchalgorithmus verwendet, um eine Schleife in einer bestimmten verknüpften Liste zu finden, und dann haben wir eine While-Schleife verwendet, um die Schleife zu durchlaufen und ihre Länge zu ermitteln. Die zeitliche Komplexität des obigen Codes beträgt O(N) und die räumliche Komplexität beträgt O(1).

Das obige ist der detaillierte Inhalt vonJavaScript-Programm zum Ermitteln der Länge einer Schleife in einer verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!