Algorithmusübungen 13

Nth from the Last Node (Easy)

Erläuterung

Da der Kopfknoten der einfach verknüpften Liste und die ganze Zahl n übergeben werden, Implementieren wir einen Algorithmus, der ** den n-ten Knoten vom Ende zurückgibt (gibt null zurück, wenn n außerhalb des Bereichs liegt).

Solution Die Idee ist, zwei Zeiger n Knoten voneinander entfernt zu verwenden. Setzen Sie zuerst den ersten Zeiger auf den Kopf und den zweiten auf den n-ten Knoten (Standardeinstellung). Wenn der zweite Knoten während der Initialisierung den Endpunkt der Liste, null, erreicht, gibt er null (außerhalb der Grenzen) zurück. Bewegen Sie dann beide Zeiger nach vorne, bis der zweite Zeiger den Endpunkt in der Schleife erreicht. Nach dem Ende der Schleife zeigt der erste Zeiger vom Ende auf den n-ten Knoten, sodass der Zeiger zurückgegeben wird. Runtime Complexity O(n) Die Ausführungszeit ist O (n), da sie in Bezug auf die Singley Linked List linear abtastet. Space Complexity O(1) Da zwei Zeiger verwendet werden, ist die Speichereffizienz eine Konstante von O (1).

Beispiel

Schauen wir uns ein Beispiel in der folgenden Liste an, das nach dem dritten und letzten Knoten sucht (n = 3). Bewegen Sie standardmäßig einen Zeiger um n Knoten. Bewegen Sie beide Zeiger vorwärts, bis der erweiterte Zeiger den Endpunkt Null erreicht. Sie haben jetzt den vorletzten Knoten gefunden.

Implementierung

lastNthFromList.java

class lastNthFromList{
  public LinkedListNode FindNthFromLast(LinkedListNode head,int n) {
    
    if (head == null || n < 1) return null; // edge case

    LinkedListNode targetNode = head;
    LinkedListNode searchNode = head;

    while (searchNode != null && n != 0) {
      searchNode = searchNode.next;
      n--;
    }

    if (n != 0) return null; // check out-of-bounds
    
    while(searchNode != null) {
      targetNode = targetNode.next;
      searchNode = searchNode.next;
    }

    return targetNode;
  }
}