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