English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية

Java Grund教程

Java-Flusssteuerung

Java Array

Java objektorientiert (I)

Java objektorientiert (II)

Java objektorientiert (III)

Java Ausnahmebehandlung

Java Liste (List)

Java Queue (Warteschlange)

Java Map-Kollektion

Java Set-Kollektion

Java Ein- und Ausgabe (I/O)

Java Reader/Writer

Andere Java-Themen

Java-Programm überprüft, ob es einen Zirkel in LinkedList gibt

Java Beispielsammlung

In diesem Beispiel werden wir lernen, wie man in Java überprüft, ob es einen Zirkel in LinkedList gibt.

Um diesen Beispiel zu verstehen, sollten Sie die folgenden Kenntnisse habenJava-ProgrammierungThema:

Beispiel: Überprüfung auf Zirkel in LinkedList

class LinkedList {
  //Erstellung eines Objekts der Klasse Node
  //Stellt den Kopf der Liste dar
  Node head;
  //Statische Innere Klasse
  static class Node {
    int value;
    //Verbindung jedes Knotens mit dem nächsten Knoten
    Node next;
    Node(int d) {
      value = d;
      next = null;
    }
  }
  //Überprüfung auf die Existenz eines Loops
  public boolean checkLoop() {
    //Erstellung von zwei Referenzen am Anfang der LinkedList
    Node first = head;
    Node second = head;
    while(first != null && first.next != null) {
      //Bewegung der ersten Referenz2Knoten
      first = first.next.next;
      //Bewegung der zweiten Referenz1Knoten
      second = second.next;
      //Wenn zwei Referenzen gleich sind (begegnen)
      if(first == second) {
        return true;
      }
    }
    return false;
  }
  public static void main(String[] args) {
    //Erstellung eines Objekts der Klasse LinkedList
    LinkedList linkedList = new LinkedList();
    //Zuweisung von Werten an jeden Knoten der Liste
    linkedList.head = new Node(1);
    Node second = new Node(2);
    Node third = new Node(3);
    Node fourth = new Node(4);
    //Verbindung jedes Knotens der Liste mit dem nächsten Knoten
    linkedList.head.next = second;
    second.next = third;
    third.next = fourth;
    //Durchlauf in der LinkedList
    fourth.next = second;
    //Druck der Knotenwerte
    System.out.print("LinkedList: ");
    int i = 1;
    while (i <= 4) {
      System.out.print(linkedList.head.value + "");
      linkedList.head = linkedList.head.next;
      i++;
    }
    //Aufruf einer Methode zur Überprüfung des Loops
    boolean loop = linkedList.checkLoop();
    if(loop) {
      System.out.println("\nEs gibt einen Zyklus im LinkedList.");
    }
    else {
      System.out.println("\nIm LinkedList gibt es keinen Zyklus.");
    }
  }
}

Ausgabefolge

LinkedList: 1 2 3 4 
Es gibt einen Zyklus im LinkedList.

Im obigen Beispiel haben wir mit Java haben LinkedList implementiert. Wir habenFloyds Algorithmus zur Zyklusfindungum zu überprüfen, ob es im LinkedList einen Zyklus gibt.

Beachten Sie den Code im checkLoop() - Methode. Hier haben wir zwei Variablen namens first, second, die Knoten im LinkedList durchsuchen.

  • first - In einer Iteration verwenden2Knoten durchsuchen

  • second - In einer Iteration verwenden1Knoten durchsuchen.

Zwei Knoten mit unterschiedlichem Tempo durchsuchen. Daher werden sie, wenn es im LinkedList einen Zyklus gibt, aufeinander treffen.

Java Beispielsammlung