Javascript-Programm zum Entfernen von Duplikaten aus sortierten verknüpften Listen

Eine verknüpfte Liste ist eine lineare Datenstruktur. Wir erhalten eine sortierte verknüpfte Liste, die aus ganzen Zahlen besteht. Es gibt einige Zahlen, die wiederholt oder wiederholt werden können, und wir müssen sie entfernen. Da die angegebene verknüpfte Liste sortiert ist, können wir sie einfach durchlaufen und mithilfe einer While-Schleife doppelte Knoten daraus entfernen. Wir werden geeigneten Code durch Diskussion der zeitlichen und räumlichen Komplexität implementieren, um die Logik besser zu verstehen.

Beispiel

Given linked list is: 1-> 2 -> 2 -> 3 -> 4 -> 4 -> 4 -> 5 -> 5 -> 5-> 6-> null
Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Erklärung – Die angegebene verknüpfte Liste ist sortiert, was das Auffinden doppelter Elemente erleichtert und wir können sie durch Überspringen entfernen, wenn sie dem vorherigen Wert entsprechen.

Sehen wir uns an, wie der Code funktioniert

Methode

Wir werden die folgenden Schritte ausführen, um das Problem zu beheben -

• Zuerst erstellen wir eine Klasse, um die Struktur für die Knoten der verknüpften Liste bereitzustellen.

• Zweitens erstellen wir Funktionen, die die verknüpfte Liste drucken und neue Knoten zur vorhandenen verknüpften Liste hinzufügen.

• Wir erstellen eine Funktion, um den Kopf der verknüpften Liste zu übergeben, aus der wir doppelte Elemente entfernen möchten, und sie gibt den Kopf der neuen verknüpften Liste zurück.

• Zuerst prüfen wir, ob die verknüpfte Liste leer ist oder ob ihre Größe gleich 1 ist. In diesen Fällen geben wir den Kopf so zurück, wie er ist.

• Wir erstellen zwei Variablen, von denen eine den Kopf und die andere den nächsten Knoten des Kopfes angibt.

• Wenn die Werte des aktuellen Knotens und des nächsten Knotens gleich sind, verschieben wir den nächsten Knoten zum nächsten Knoten und aktualisieren die Adresse des nächsten Knotens des aktuellen Knotens.

• Andernfalls bewegen wir uns zum nächsten Knoten und verschieben den nächsten Knoten zu seinem nächsten Knoten.

• Abschließend kehren wir zur Kopfzeile zurück und drucken den darin enthaltenen Wert aus.

Beispiel

Lassen Sie uns die angegebenen Schritte zum besseren Verständnis im Code implementieren

// class to provide structure to linked list node
class Node{
   constructor(val){
      this.value = val
      this.next = null
   }
}
// function to print the linked list
function print(head){
   var temp = head;
   if(head == null){
      console.log("The given linked list is empty");
   } else {
      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){
   var new_node = new Node(data);
   if(head == null){
      head = new_node
      return new_node
   } else {
      tail.next = new_node;
      return new_node
   }
}
// function to remove the duplicate numbers 
function removeDupli(head){
   // if linked list is empty 
   if(head == null){
      return head;
   }
   // if linked list is of size one 
   if(head.next == null){
      return head;
   }
   var temp = head
   var next = head.next
   while(next != null){
      if(temp.value == next.value){
         next = next.next;
         temp.next = next;
      } else {
         next = next.next;
         temp = temp.next;
      }
   }
   return head;
}
// defining linked list
var head  = new Node(1)
var tail  = head
tail = add(2,head, tail)
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(4,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(5,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
console.log("The given linked list is: ")
print(head)
// calling function to remove duplicate elements 
head = removeDupli(head)
console.log("The Linked list after removal of duplicate integers is: ")
print(head)

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N), wobei N die Gesamtzahl der Knoten in der angegebenen verknüpften Liste ist. Die zeitliche Komplexität ist linear, da wir die verknüpfte Liste nur einmal durchlaufen.

Die Speicherplatzkomplexität des obigen Codes beträgt O(1), da wir keinen zusätzlichen Speicherplatz verwenden.

Fazit

In diesem Tutorial haben wir ein JavaScript-Programm implementiert, um doppelte Elemente aus einer bestimmten sortierten verknüpften Liste zu entfernen. Da die verknüpfte Liste sortiert ist, liegen alle doppelten Elemente nebeneinander und können durch Durchlaufen leicht entfernt werden. Die zeitliche Komplexität des von uns implementierten Programms beträgt O(N) und die räumliche Komplexität beträgt O(1).

Das obige ist der detaillierte Inhalt vonJavascript-Programm zum Entfernen von Duplikaten aus sortierten verknüpften Listen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!