English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
Dans cet exemple, nous allons apprendre à détecter si une boucle existe dans LinkedList en Java.
Pour comprendre cet exemple, vous devriez comprendre ce qui suitProgrammation JavaThème :
class LinkedList { //Créer un objet de la classe Node //Représente la tête de la liste chaînée Node head; //Classe interne statique static class Node { int value; //Connecter chaque noeud à son noeud suivant Node next; Node(int d) { value = d; next = null; } } //Vérifier l'existence d'un cycle public boolean checkLoop() { //Créer deux références à l'origine de LinkedList Node first = head; Node second = head; while(first != null && first.next != null) { //Déplacer la première référence2un noeud first = first.next.next; //Déplacer la deuxième référence1un noeud second = second.next; //Si deux références sont égales (rencontre) if(first == second) { return true; } } return false; } public static void main(String[] args) { //Créer un objet LinkedList LinkedList linkedList = new LinkedList(); //Affecter des valeurs à chaque noeud de la liste chaînée linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); Node fourth = new Node(4); //Connecter chaque noeud de la liste chaînée au noeud suivant linkedList.head.next = second; second.next = third; third.next = fourth; //Effectuer une boucle dans LinkedList fourth.next = second; //Imprimer la valeur du noeud System.out.print("LinkedList: "); int i = 1; while (i <= 4) { System.out.print(linkedList.head.value + ""); linkedList.head = linkedList.head.next; i++; } //Appel de méthode pour vérifier le cycle boolean loop = linkedList.checkLoop(); if(loop) { System.out.println("\nThere is a loop in LinkedList."); } else { System.out.println("\nThere is no loop in LinkedList."); } } }
Output result
LinkedList: 1 2 3 4 There is a loop in LinkedList.
. In the above example, we have used Java we have implemented LinkedList. We have usedFloyd's loop search algorithmto check if there is a loop in LinkedList.
Note the code in the checkLoop() method. Here, we have two variables named first, second, which traverse the nodes in LinkedList.
first - in a single iteration2nodes for traversal
second - in a single iteration1nodes for traversal.
Two nodes traverse at different speeds. Therefore, if there is a loop in LinkedList, they will meet.