Entfernen von Duplikaten aus einer Linked-List in Java ohne die Verwendung von Extra-Puffer

Question

Ich überprüfe einige Codeschnipsel für einen kommenden Test. Ich habe das in meinen Notizen gesehen und habe gerade gemerkt, dass dieser Code für Methode 1 keine Duplikate entfernt, wenn die Liste auf diese Weise A -> B -> C -> A ist. Ich habe eine alternative Funktion geschrieben (Methode 2) Ich denke, dass es funktionieren wird. Was denkt ihr? Funktioniert Methode 1 tatsächlich nicht und ich verfolge es falsch? p.s. Wir sind zu diesem Zeitpunkt keine Compiler erlaubt :)

Hier ist der Code, und eine kurze Einführung dessen, was es tun soll.

METHODE 1: Was ich denke, funktioniert nicht, wenn es 2 genaue Dinge an Kopf und Schwanz gibt. Code schreiben, um Duplikate aus einer unsortierten Liste OHNE Puffer zu entfernen. Wwe kann mit zwei Zeigern iterieren: "current" führt eine normale Iteration aus, während "runner" alle vorherigen Knoten durchläuft, um nach "dups" zu suchen. Runner wird nur einen Dup pro Knoten sehen, denn wenn mehrere Duplikate vorhanden wären, wären sie bereits entfernt worden.

public static void deleteDuplicates1(LinkedListNode head) { 
if (head == null) return; 
LinkedListNode previous = head; 
LinkedListNode current = previous.next; 
while (current != null) { 
    LinkedListNode runner = head; 
     while (runner != current) { // Check for earlier dups 
      if (runner.data == current.data) { 
       LinkedListNode tmp = current.next; // remove current 
       previous.next = tmp; 
       current = tmp; // update current to next node 
       break; // all other dups have already been removed 
       } 
       runner = runner.next; 
      } 
      if (runner == current) { // current not updated - update now 
       previous = current; 
       current = current.next; 
       } 
     } 
} 

Ich dachte, das würde funktionieren. Methode 2:

public void removeDuplicates2(){ 
    Node current = null; 
    Node tracer = null; 

    for(current = head.next; current!=null; current=current.next){ 
     for(tracer=head; tracer!=current; tracer=tracer.next){ 
      if(tracer.data == current.data) 
      //DELETE THE NODE IN CURRENT 
     } 
    } 

} 

Answer 1

Ich bin mir nicht sicher, was „ohne zusätzlichen Puffer“ bedeutet für Sie, aber da ich ein fauler Mensch bin und da ich andere Leute denken, sind weit besser auf Algorithmen als ich das Schreiben aus , Würde ich die gesamte verknüpfte Liste in ein HashSet und zurück zu einer verknüpften Liste setzen. Das wird Duplikate leicht entfernen:

LinkedList result = new LinkedList(new HashSet(inputList)); 

Oder, wenn Sie die Reihenfolge der Elemente

LinkedList result = new LinkedList(new LinkedHashSet(inputList)); 

Jetzt erhalten wollen, da dies eine Hausaufgaben Frage ist, und Sie scheinen eine LinkedList sich umsetzen, kann es gut, dass diese Lösung nicht machbar ist ;-) Aber in jedem Fall wird es von O (n) Komplexität sein, und nicht O (n^2) wie Ihre beiden Methoden 1 und 2, die schon viel besser sein könnten Sie...?

Answer 2

Der beste Weg ist die verknüpfte Liste zu sortieren. dann iterieren und prüfen, ob benachbarte Elemente gleich sind. Wenn ja, löschen Sie das angrenzende Element. Dies ist eine O (nlogn) -Methode, ohne einen zusätzlichen Puffer zu verwenden.

Answer 3

Ich habe meinen Code hier hinzugefügt, aber ich bin verwirrt über die Zeit Komplexität wird es O (n) oder O (n log n) sein? Lass es mich wissen.

public Node removeDuplicatesFromUnsortedLinkedListWithoutExtraSpace(Node head) 
{ 
    if(head == null || head.next == null) 
     return head; 

    Node prev = head; 
    Node curr = head.next; 
    Node temp = curr; 

    while(prev.next!=null) 
    { 
     if(prev.data == curr.data) 
     { 
      temp.next = curr.next; 
      curr = curr.next; 
     } 
     else 
     { 
      if(curr != null) 
      { 
       temp = curr; 
       curr = curr.next; 
      } 

      if(curr == null) 
      { 
       prev = prev.next; 
       curr = prev.next; 
       temp = curr; 
      } 
     } 
    } 
    return head; 
} 

Answer 4

Modifikation gemacht oben auf die Funktion der Logik zu korrigieren, aber ich bin nicht sicher, was die Zeitkomplexität der Funktion ist. Ist es in O (n^2) oder O (n)

public static removeDuplicatesFromUnsortedLinkedListWithoutExtraSpace Knoten (Node Kopf) { if (Kopf == null || head.next == null) return Kopf;

Node prev = head; 
    Node curr = head.next; 
    Node temp = prev; 

    while(prev.next!=null){ 
     if(curr != null){ 
      if(prev.data == curr.data){ 
       temp.next = curr.next; 
       curr = curr.next; 
      }else { 
       temp = curr; 
       curr = curr.next; 
      } 
     }else{ 
      prev = prev.next; 
      curr = prev.next; 
      temp = prev; 
     } 
    } 
    return head; 
} 

Answer 5

public static Node removeDuplicates(Node head) { 
    Node cur = head; 
    Node next = cur.next; 
    while (cur != null && cur.next != null) { 
     next = cur; 
     while (next.next != null) { 
      if (cur.data == next.next.data) { 
       Node d = next.next; 
       next.next = next.next.next; 
      } else { 
       next = next.next; 
      } 
     } 
     cur = cur.next; 
    } 
    return head; 
} 

Diese verwenden die Doppelzeiger-Methode. Ohne zusätzlichen Speicherplatz zu verwenden, können wir zwei Punkte (langsam) und die nächsten (schnell) Zeiger haben. Für jeden Zeiger werden die Daten im nächsten Zeiger überprüft. Wenn eine Übereinstimmung gefunden wird, werden die Zeiger so eingestellt, dass sie auf den nächsten jeweiligen Knoten zeigen. Hoffe das hilft.