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
C++
// C++ program to count number of nodes
// in loop in a linked list if loop is
// present
#include<bits/stdc++.h>
using namespace std;
// Link list node
struct Node
{
int data;
struct Node* next;
};
// Returns count of nodes present
// in loop.
int countNodes(struct Node *n)
{
int res = 1;
struct 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 */
int countNodesinLoop(struct Node *list)
{
struct Node *slow_p = list,
*fast_p = list;
while (slow_p &&
fast_p &&
fast_p->next)
{
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;
}
struct Node *newNode(int key)
{
struct Node *temp =
(struct Node*)malloc(sizeof(struct Node));
temp->data = key;
temp->next = NULL;
return temp;
}
// Driver Code
int main()
{
struct 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;
cout << countNodesinLoop(head) << endl;
return 0;
}
// This code is contributed by SHUBHAMSINGH10
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