Subtrahieren der verknüpften Liste Knoten

Question

Ich versuche, eine verknüpfte Liste Problem zu lösen. Bei einer einfach verknüpften Liste, ändern Sie den Wert der ersten Halb Knoten, so dass:

ersten Knotens neuen Wert = der Wert des letzten Knoten - erste Stromwert des Knotens

zweiten Knotens neuen Wert = der zweiten letzten Knotens Wert - 2. Knoten aktuelle Wert

Beispiel:

Bei verketteten Liste 1 -> 2 -> 3 -> 4 -> 5,

Sie kehren sollen 4 -> 2 -> 3 -> 4 -> 5

Bisher Lösung, die ich denken konnte, ist

1. Iterate der LinkedList die Länge zu finden.
2. Iterieren Sie die zweite Hälfte der verketteten Liste, um die Knotenwerte in einen Stapel zu schieben
3. Iterieren Sie die erste Hälfte der Liste, pop den Stapel, subtrahieren Sie die Knotenwerte.

Wahrscheinlich ist dies die naivste Lösung. Kann annyone bitte vorschlagen eine effizientere Lösung in Bezug auf Zeit/Raum (mehrere Wiederholungen und zusätzlichen Platz für Stapel vermeiden wollen)? Danke im Voraus.

Antwort:

public ListNode subtract(ListNode a) { 

     ListNode slow =a; 
     ListNode fast=a; 


     ListNode head = a; 

     ListNode middle = null; 

     while(fast!=null && fast.next!=null) 
      { 

       if(fast.next.next!=null) // in case numOfNodes are even , we need to stay at middle 
        slow=slow.next; 
       fast = fast.next.next; 

      } 
     if(slow==fast) 
      return a; 

     middle = slow; 
     ListNode secondHalf = middle.next; 
     middle.next = null; 

     ListNode reversed = reverse(secondHalf); 

     ListNode temp1 = reversed; 

     while(temp1!=null){ 
      head.val = temp1.val - head.val; 
      temp1 = temp1.next; 
      head = head.next; 
     } 

     middle.next = reverse(reversed); 


     return a; 

    } 


    public ListNode reverse(ListNode head){ 
     ListNode current = head; 
     ListNode previous = null; 

     while(current!=null) { 
      ListNode temp = current.next; 
      current.next = previous; 
      previous = current; 
      current = temp; 

     } 

     return previous; 
    } 

Answer 1

Wenn Sie die Liste dann zu ändern, erlaubt es eine bessere Lösung mit konstanten zusätzlichen Platz als die, die ich in den Kommentaren erwähnt:

1. die Mitte finden .

2. Kehren Sie die Liste von der Mitte nach rechts um.

3. Führen Sie die Subtraktionen durch, indem Sie die beiden Listen Schritt für Schritt durchgehen.

4. Umkehren/verbinden Sie die Listen wieder zurück, um die ursprüngliche Listenreihenfolge zu erhalten.

All diese Schritte erfordern O (1) Raum und O (n) Zeit, damit der Algorithmus Gesamt erfordern auch O (1) Raum und O (n) Zeit.

Dies ist nur ein Umriss des Algorithmus zu beweisen, dass es in O (n) Zeit mit constanst zusätzlichen Raum möglich ist, gibt es einige Fallen wie gerade/ungerade Anzahl von Elementen usw.

Es könnte einige Raum für Verbesserungen, aber Sie können nicht besser als O (n) Zeit, weil das Finden des letzten Elements oder das Durchführen der Subtraktionen bereits O (n) Zeit erfordert.

Answer 2

Sie können eine rekursive Funktion schreiben, die dieses Problem ohne zusätzlichen Speicherplatz löst, d. H. Wenn Sie den Stack-Frame nicht als zusätzlichen Speicherplatz betrachten.

Der Code ist in C# geschrieben, aber Sie sollten in der Lage sein, die Sprache, die Sie benötigen, einfach zu übersetzen.

Ein Vorbehalt bei diesem Ansatz besteht darin, dass Sie den aktuellen Knoten, auf dem wir uns befinden, mit einer globalen Variablen verfolgen müssen.

static ListNode<int> temp = list.head; // Point to first element in the list 
private static int reverse(ListNode<int> listNode, int currentNode, int totalNodes) 
{ 
    if (listNode == null) 
    { 
     return 0; 
    } 
    currentNode = reverse(listNode.next, currentNode, totalNodes + 1); 
    if (currentNode < totalNodes) //To check if half is reached 
    { 
     temp.data = listNode.data - temp.data; 
     temp = temp.next; 
    } 
    return ++currentNode; 
} 

Sie können diese Methode als solche reverse(list.head, 0, 0); aufrufen und den Rückgabewert ignorieren oder es irgendwo speichern, wie es bis in die Mitte der verknüpften Liste zeigt, die irgendwo nützlich sein könnte später.

Mit der Standardimplementierung der verknüpften Liste bezweifle ich, wenn Sie in der Lage sein werden, Raum/Zeit-Komplexität besser als diese zu erreichen.

Sie können die globale Variable ersetzen und als Argument übergeben, wenn Sie die Implementierung von ListNode so ändern können, dass sie auch den Index dieses Knotens enthält.