En este ejemplo, aprenderemos a detectar si hay un bucle en LinkedList en Java.
Para comprender este ejemplo, debe tener el conocimiento de los siguientes temas de programación de Java:
- LinkedList de Java
- Métodos Java
Ejemplo: detectar bucle en una LinkedList
class LinkedList ( // create an object of Node class // represent the head of the linked list Node head; // static inner class static class Node ( int value; // connect each node to next node Node next; Node(int d) ( value = d; next = null; ) ) // check if loop is present public boolean checkLoop() ( // create two references at start of LinkedList Node first = head; Node second = head; while(first != null && first.next !=null) ( // move first reference by 2 nodes first = first.next.next; // move second reference by 1 node second = second.next; // if two references meet // then there is a loop if(first == second) ( return true; ) ) return false; ) public static void main(String() args) ( // create an object of LinkedList LinkedList linkedList = new LinkedList(); // assign values to each linked list node linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); Node fourth = new Node(4); // connect each node of linked list to next node linkedList.head.next = second; second.next = third; third.next = fourth; // make loop in LinkedList fourth.next = second; // printing node-value System.out.print("LinkedList: "); int i = 1; while (i <= 4) ( System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; i++; ) // call method to check loop boolean loop = linkedList.checkLoop(); if(loop) ( System.out.println("There is a loop in LinkedList."); ) else ( System.out.println("There is no loop in LinkedList."); ) ) )
Salida
LinkedList: 1 2 3 4 Hay un bucle en LinkedList.
En el ejemplo anterior, hemos implementado una LinkedList en Java. Hemos utilizado el algoritmo de búsqueda de ciclos de Floyd para comprobar si hay un bucle en LinkedList.
Observe el código dentro del checkLoop()método. Aquí, tenemos dos variables denominadas primero y segundo que atraviesan los nodos en LinkedList.
- primero : atraviesa con 2 nodos en una sola iteración
- segundo - atraviesa con 1 nodo en una sola iteración
Dos nodos atraviesan a diferentes velocidades. Por lo tanto, se encontrarán si hay un bucle LinkedList.
