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
Javascript
<script>
// Javascript program to count number of nodes
// in loop in a linked list if loop is
// present
// Link list node
class Node
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
// Returns count of nodes present in loop.
function countNodes(n)
{
var res = 1;
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 */
function countNodesinLoop(list)
{
var 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;
}
function newNode(key)
{
temp = new Node(key);
return temp;
}
// Driver code
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;
document.write(countNodesinLoop(head));
// This code contributed by gauravrajput1
</script>
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