English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
In questo esempio, impareremo a rilevare se esiste un ciclo in LinkedList Java.
Per comprendere questo esempio, dovresti conoscere il seguenteProgrammazione JavaArgomento:
class LinkedList { //创建Node类的对象 //表示链表的头部 Node head; //静态内部类 static class Node { int value; //Connetti ogni nodo con il successivo Node next; Node(int d) { value = d; next = null; } } //Controlla se esiste un ciclo public boolean checkLoop() { //Crea due riferimenti all'inizio della LinkedList Node first = head; Node second = head; while(first != null && first.next != null) { //Sposta il primo riferimento di due nodi first = first.next.next; //Sposta il secondo riferimento di un nodo second = second.next; //Se due riferimenti sono uguali (incontro) if(first == second) { return true; } } return false; } public static void main(String[] args) { //Crea un oggetto LinkedList LinkedList linkedList = new LinkedList(); //Assegna un valore a ogni nodo della lista linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); Node fourth = new Node(4); //Connetti ogni nodo della lista con il successivo linkedList.head.next = second; second.next = third; third.next = fourth; //Esegui un ciclo nella LinkedList fourth.next = second; //Stampa il valore del nodo System.out.print("LinkedList: "); int i = 1; while (i <= 4) { System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; i++; } //Chiamata al metodo per controllare il ciclo boolean loop = linkedList.checkLoop(); if(loop) { System.out.println("\nC'è un ciclo nella LinkedList."); } else { System.out.println("\nNon ci sono cicli nella LinkedList."); } } }
Risultato di output
LinkedList: 1 2 3 4 In LinkedList c'è un ciclo.
Nell'esempio sopra, abbiamo utilizzato Java Implementato LinkedList. Abbiamo utilizzatoAlgoritmo di ricerca di ciclo di Floydper verificare se LinkedList ha un ciclo.
Attenzione al codice nel metodo checkLoop(). Qui abbiamo due variabili chiamate first, second che esplorano i nodi di LinkedList.
first - Utilizzare due nodi per esplorare durante un'iterazione singola
second - Utilizzare un singolo nodo per esplorare durante un'iterazione singola.
Due nodi esplorano a velocità diverse. Pertanto, se LinkedList ha un ciclo, si incontreranno.