¿Cuál es la mejor (interrumpiendo) algoritmo para determinar si una lista enlazada tiene un ciclo?
[Editar] Análisis de la complejidad asintótica para el tiempo y el espacio sería dulce de modo que las respuestas se pueden comparar mejor.
[Editar] pregunta Original no era el direccionamiento de los nodos con outdegree > 1, pero hay algunos a hablar de ello. Esa pregunta es más a lo largo de las líneas de "Mejor algoritmo para detectar ciclos en el grafo dirigido".
Tiene dos punteros de la iteración a través de la lista; hacer una iterar a través de dos veces la velocidad de la otra, y comparar sus posiciones en cada paso. La parte superior de mi cabeza, algo así como:
node* tortoise(begin), hare(begin);
while(hare = hare->next)
{
if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
hare = hare->next;
if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
tortoise = tortoise->next;
}
O(n), que es tan bueno como usted puede conseguir.
Condición previa: seguir la pista de el tamaño de la lista (actualizar el tamaño de whenenver un nodo se agrega o elimina).
Detección de bucle:
Mantener un contador cuando se atraviesa el tamaño de la lista.
Si el contador supera el tamaño de la lista, hay un posible ciclo.
Complejidad: O(n)
Nota: la comparación entre el contador y el tamaño de la lista, así como la operación de actualización de la lista tamaño, debe ser seguro para subprocesos.
Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.
