Java-Codebeispiel zur Implementierung einer umgekehrt verknüpften Liste

In diesem Artikel wird hauptsächlich das Codebeispiel für die Implementierung einer umgekehrt verknüpften Liste in der Java-Sprache vorgestellt. Der Herausgeber findet es ziemlich gut, daher werde ich es hier als Referenz für Freunde teilen, die es benötigen.

Problembeschreibung

Definieren Sie eine Funktion, die den Kopfknoten einer verknüpften Liste eingibt, die verknüpfte Liste umkehrt und den Kopfknoten der umgekehrten verknüpften Liste ausgibt. Die verknüpften Listenknoten lauten wie folgt:

public class ListNode {
  int val;
  ListNode next = null;
  ListNode(int val) {
    this.val = val;
  }
}

Idee 1:

Um die verknüpfte Liste umzukehren, für Knoten i , wir Um es auf seinen Vorgänger zu verweisen, müssen wir den Vorgängerknoten speichern. Wenn wir gleichzeitig den Nachfolger von i neu zugewiesen haben, können wir ihn nicht finden Ich muss meinen Nachfolger retten.

Code:

public ListNode ReverseList(ListNode head) {
    if(head == null){
      return null;
    }
    ListNode rHead = null;
    ListNode prior = null;//store prior
    ListNode q = head;//store current
    while(q != null){
      ListNode next = q.next;//store the next
      if(next == null){
        rHead = q;
      }
      q.next = prior;
      prior = q;
      q = next;
    }
    return rHead;
  }

Idee 2:

Verwenden Sie die Idee der Rekursion (I Ich habe noch nicht darüber nachgedacht, denn wenn Rekursion verwendet wird, sollte es jedes Mal sein: der erste Knoten der verknüpften Liste – der Endzeiger der durch die Rekursion zurückgegebenen verknüpften Liste, aber in diesem Fall kann der umgekehrte Kopfzeiger nicht sein erhalten.) Lassen Sie uns später darüber nachdenken.

Zusammenfassung

Das obige ist der detaillierte Inhalt vonJava-Codebeispiel zur Implementierung einer umgekehrt verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!