English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
Neste exemplo, vamos aprender a detectar se existe loop no LinkedList do Java.
Para entender este exemplo, você deve conhecer o seguinteProgramação JavaTema:
class LinkedList { //Criar objeto da classe Node //Representa a cabeça da lista Node head; //Classe interna estática static class Node { int value; //Conectar cada nó ao nó seguinte Node next; Node(int d) { value = d; next = null; } } //Verificar se há loop public boolean checkLoop() { //Criar duas referências no início de LinkedList Node first = head; Node second = head; while(first != null && first.next != null) { //Mover a primeira referência2nó first = first.next.next; //Mover a segunda referência1nó second = second.next; //Se os dois referenciadores forem iguais (encontrado) if(first == second) { return true; } } return false; } public static void main(String[] args) { //Criar objeto LinkedList LinkedList linkedList = new LinkedList(); //Atribuir valor a cada nó da lista encadeada linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); Node fourth = new Node(4); //Conectar cada nó da lista encadeada ao nó seguinte linkedList.head.next = second; second.next = third; third.next = fourth; //Realizar loop em LinkedList fourth.next = second; //Imprimir valor do nó System.out.print("LinkedList: "); int i = 1; while (i <= 4) { System.out.print(linkedList.head.value + ""); linkedList.head = linkedList.head.next; i++; } //Chama método para verificar loop 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 implemented LinkedList. We usedFloyd's Cycle Detection 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.