Java implementiert die gemeinsame Nutzung von Beispielcode für die Ausgabe des k-ten Knotens am Ende einer verknüpften Liste

In diesem Artikel wird hauptsächlich der relevante Inhalt des k-ten Knotens am Ende der verknüpften Java-Ausgabeliste vorgestellt. Er umfasst drei Designideen und Codebeispiele. Er hat einen gewissen Referenzwert und kann von Freunden in Anspruch genommen werden.

Problembeschreibung

Geben Sie eine verknüpfte Liste ein und geben Sie den k-ten Knoten vom letzten in der verknüpften Liste aus. (Der letzte Knoten ist der letzte)

Der Knoten ist wie folgt definiert:

public class ListNode {
  int val;
  ListNode next = null;

  ListNode(int val) {
    this.val = val;
  }
}

Idee 1:

Durchlaufen Sie zuerst die verknüpfte Liste und berechnen Sie ihre Länge.
Berechnen Sie dann, dass der k-te Knoten vom letzten die positive Länge hat – k + 1.
Durchlaufen Sie abschließend die verknüpfte Liste und finden Der erforderliche Knoten
hat eine zeitliche Komplexität von O(2n) und muss die verknüpfte Liste zweimal durchlaufen

Der Code lautet wie folgt:

public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null || k <= 0){
      return null;
    }
    //直接遍历
    ListNode p = head;
    int length = 1;
    while(p.next != null){
      length++;
      p = p.next;
    }
    int index = length - k + 1;
    if(index <= 0){
      return null;
    }
    p = head;
    int num = 1;
    while(p.next != null && num < index){
      num++;
      p = p.next;
    }
    if(num < index){
      return null;
    }else{
      return p;
    }
  }

Idee 2:

Erwarten Sie, dass Sie es erhalten, indem Sie die verknüpfte Liste nur einmal durchlaufen.
Setzen Sie zwei Zeiger, einen so initialisiert, dass er auf den ersten Knoten zeigt, und den zweiten auf den k-ten Knoten. Dann bewegen sich die beiden Zeiger synchron rückwärts. Wenn der zweite Zeiger auf den Endknoten zeigt, zeigt der erste Zeiger auf den k-ten Knoten von unten

Code:

public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null || k <= 0){
      return null;
    }
    //直接遍历
    ListNode p = head;
    ListNode q = head;
    for(int i = 0; i < k-1; i++){
      if(q == null){
        return null;
      }
      q = q.next;
    }
    if(q == null){
      return null;
    }
    while(q.next != null){
      p = p.next;
      q = q.next;
    }
    return p;
  }

Idee 3:

Kehren Sie die verknüpfte Liste um, dann besteht das ursprüngliche Problem darin, den k-ten positiven Knotenpunkt zu finden.
Dies ändert jedoch die ursprüngliche verknüpfte Liste und ist nicht effizienter als Idee 2

Umkehrung der verknüpften Liste: siehe „Java-Sprachimplementierung des Codebeispiels für umgekehrt verknüpfte Listen“

Zusammenfassung

Das obige ist der detaillierte Inhalt vonJava implementiert die gemeinsame Nutzung von Beispielcode für die Ausgabe des k-ten Knotens am Ende einer verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!