Escriba una función detectAndCountLoop() que verifique si una lista enlazada dada contiene un bucle y, si el bucle está presente, devuelve el recuento de Nodes en el bucle. Por ejemplo, el bucle está presente en la lista de enlaces a continuación y la longitud del bucle es 4. Si el bucle no está presente, la función debería devolver 0.
Enfoque:
Se sabe que el algoritmo de detección del ciclo de Floyd termina cuando los punteros rápido y lento se encuentran en un punto común. También se sabe que este punto común es uno de los Nodes del bucle. Almacene la dirección de este punto común en una variable de puntero, digamos (ptr). Luego inicialice un contador con 1 y comience desde el punto común y continúe visitando el siguiente Node y aumentando el contador hasta que se alcance nuevamente el puntero común.
En ese punto, el valor del contador será igual a la longitud del bucle.
Algoritmo:
- Encuentre el punto común en el bucle utilizando el algoritmo de detección del ciclo de Floyd
- Almacene el puntero en una variable temporal y mantenga un conteo = 0
- Recorra la lista enlazada hasta que se vuelva a alcanzar el mismo Node y aumente el conteo mientras pasa al siguiente Node.
- Imprimir el conteo como longitud de bucle
Java
// Java program to count number of nodes
// in loop in a linked list if loop is
// present
import java.io.*;
class GFG
{
// Link list node
static class Node
{
int data;
Node next;
Node(int data)
{
this.data =data;
next =null;
}
}
// Returns count of nodes present
// in loop.
static int countNodes( Node n)
{
int res = 1;
Node temp = n;
while (temp.next != n)
{
res++;
temp = temp.next;
}
return res;
}
/* This function detects and counts
loop nodes in the list. If loop
is not there in then returns 0 */
static int countNodesinLoop( Node list)
{
Node slow_p = list,
fast_p = list;
while (slow_p !=null &&
fast_p!=null &&
fast_p.next!=null)
{
slow_p = slow_p.next;
fast_p = fast_p.next.next;
/* If slow_p and fast_p meet at some
point then there is a loop */
if (slow_p == fast_p)
return countNodes(slow_p);
}
// Return 0 to indicate that there is
// no loop
return 0;
}
static Node newNode(int key)
{
Node temp = new Node(key);
return temp;
}
// Driver code
public static void main (String[] args)
{
Node head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(3);
head.next.next.next = newNode(4);
head.next.next.next.next = newNode(5);
// Create a loop for testing
head.next.next.next.next.next = head.next;
System.out.println( countNodesinLoop(head));
}
}
// This code is contributed by inder_verma.
Producción:
4
Análisis de Complejidad:
- Complejidad temporal: O(n).
Solo se necesita un recorrido de la lista enlazada. - Espacio Auxiliar: O(1).
Como no se requiere espacio adicional.
¡ Consulte el artículo completo sobre Encontrar la longitud del bucle en la lista vinculada para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA