Algorithmusgymnastik 11

Remove Duplicates from a Linked List Scannen Sie vom Kopf der LinkedList, löschen Sie alle doppelten Knoten und geben Sie den Kopf der LinkedList ohne Duplikate zurück.

Erläuterung

Angesichts der folgenden LinkedList: Wenn Sie 28 und 14 mit doppelten Daten löschen, erhalten Sie die folgende verknüpfte Liste. Solution Runtime Complexity O(n) Die Ausführungszeit beträgt O (n), da die unsortierte LinkedList nach Duplikaten durchsucht wird. Space Complexity O(n) Die Datenstruktur von HashSet wird verwendet, um zu unterscheiden, ob es dupliziert wird, und wenn keine duplizierten Daten vorhanden sind, ist das schlechteste O (n).

Implementierung

removeDuplicate.java

class removeDuplicate{
  public LinkedListNode remove_duplicates(LinkedListNode head) 
  {
    if (head == null || head.next == null) {
      return head;
    }

    LinkedListNode cur = head;
    LinkedListNode prev = head;

    HashSet set = new HashSet();

    while (cur != null) {
      if (!set.contains(cur.data)) {
        set.add(cur.data);
        prev = cur;
      } else {
        prev.next = cur.next;
      }
      cur = cur.next;
    }
    return head;
  }
}

Gedanken

Der Algorithmus ist einfach und verwendet zwei Zeiger, um das HashSet zu füllen. Wenn der Zeiger und der Cur auf doppelte Daten stoßen, verwenden Sie den Zeiger und setzen Sie diesen Punkt auf den Knoten unmittelbar vor dem Cur. Prev.next = cur.next überspringt Knoten mit doppelten Daten. Wenn genügend Speicher vorhanden ist, gibt es meiner Meinung nach kein Problem mit einer solchen Implementierung.

Wenn Sie jedoch nur über begrenzten Speicher verfügen, müssen Sie die Ausführungszeit opfern. Wenn Sie die LinkedList neu anordnen dürfen, können Sie nach O (n logn) Zeit sortieren. Nach dem Sortieren sind die Knoten, die alle doppelten Daten enthalten, benachbart und können mit einem linearen Scan entfernt werden.

Wenn eine Nachbestellung nicht zulässig ist Für jeden Knoten in der LinkedList wird nach Knoten im vorherigen Knoten gesucht, die dieselben Daten enthalten. Dieser Algorithmus ist O (n ^ 2) und benötigt keinen zusätzlichen Speicherplatz, jedoch auf Kosten einer signifikanten Ausführungszeit.