El mejor algoritmo para probar si una lista enlazada tiene un ciclo

StackOverflow https://stackoverflow.com/questions/34249

Pregunta

¿Cuál es el mejor algoritmo (detención) para determinar si una lista vinculada tiene un ciclo?

[Editar] El análisis de la complejidad asintótica tanto para el tiempo como para el espacio sería bueno para que las respuestas se puedan comparar mejor.

[Editar] La pregunta original no abordaba los nodos con grado superior> 1, pero se habla un poco al respecto.Esa pregunta se parece más a "El mejor algoritmo para detectar ciclos en un gráfico dirigido".

¿Fue útil?

Solución

Tener dos punteros recorriendo la lista;haga que uno repita al doble de velocidad que el otro y compare sus posiciones en cada paso.Fuera de mi cabeza, algo 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 lo mejor que puedes conseguir.

Otros consejos

Condición previa:Realice un seguimiento del tamaño de la lista (actualice el tamaño cada vez que se agregue o elimine un nodo).

Detección de lazo:

  1. Mantenga un contador al recorrer el tamaño de la lista.

  2. Si el contador excede el tamaño de la lista, existe un posible ciclo.

Complejidad:En)

Nota:la comparación entre el contador y el tamaño de la lista, así como la operación de actualización del tamaño de la lista, deben ser seguras para subprocesos.

Tome 2 punteros *p y *q, comience a recorrer la lista vinculada "LL" usando ambos punteros:

1) el puntero p eliminará el nodo anterior cada vez y apuntará al siguiente nodo.

2) el puntero q irá cada vez solo en dirección de avance.

condiciones:

1) el puntero p apunta a nulo y q apunta a algún nodo:El bucle está presente

2) ambos punteros apuntan a nulo:no hay bucle

¿Qué tal si usamos una tabla hash para almacenar los nodos ya vistos (los miras en orden desde el principio de la lista)?En la práctica, podría lograr algo cercano a O(N).

De lo contrario, utilizar un montón ordenado en lugar de una tabla hash lograría O(N log(N)).

Me pregunto si hay alguna otra manera además de hacerlo de forma iterativa: llenar una matriz a medida que avanza y verificar si el nodo actual ya está presente en la matriz...

El algoritmo de Konrad Rudolph no funcionará si el ciclo no apunta al principio.La siguiente lista lo convertirá en un bucle infinito:1->2->3->2.

El algoritmo de DrPizza es definitivamente el camino a seguir.

En este caso, el código de OysterD será la solución más rápida (coloración de vértices)

Eso realmente me sorprendería.Mi solución realiza como máximo dos pases a través de la lista (si el último nodo está vinculado al penúltimo veta) y, en el caso común (sin bucle), realizará solo un pase.Sin hash, sin asignación de memoria, etc.

En este caso, el código de OysterD será la solución más rápida (coloración de vértices)

Eso realmente me sorprendería.Mi solución realiza como máximo dos pases a través de la lista (si el último nodo está vinculado al penúltimo veta) y, en el caso común (sin bucle), realizará solo un pase.Sin hash, sin asignación de memoria, etc.

Sí.Me di cuenta de que la formulación no era perfecta y la reformulé.Sigo creyendo que un hash inteligente podría funcionar más rápido... por un pelo.Creo en tu algoritmo es Sin embargo, la mejor solución.

Sólo para subrayar mi punto:La coloración vertec se utiliza para detectar ciclos en dependencias por parte de los recolectores de basura modernos, por lo que existe un caso de uso muy real para ello.En su mayoría utilizan banderas de bits para realizar la coloración.

Tendrá que visitar cada nodo para determinar esto.Esto se puede hacer de forma recursiva.Para evitar que visites nodos ya visitados, necesitas una bandera que diga "ya visitado".Por supuesto, esto no te da bucles.Entonces, en lugar de una bandera de bits, use un número.Empieza en 1.Verifique los nodos conectados y luego márquelos como 2 y recurra hasta que la red esté cubierta.Si al verificar los nodos encuentra un nodo que es más de uno menos que el nodo actual, entonces tiene un ciclo.La duración del ciclo está dada por la diferencia.

Se inicializan dos punteros al principio de la lista.Un puntero avanza una vez en cada paso y el otro avanza dos veces en cada paso.Si el puntero más rápido vuelve a encontrarse con el más lento, hay un bucle en la lista.De lo contrario, no habrá bucle si el más rápido llega al final de la lista.

El código de muestra siguiente se implementa de acuerdo con esta solución.El puntero más rápido es pFast y el más lento es pSlow.

bool HasLoop(ListNode* pHead)
{
    if(pHead == NULL)
        return false;


    ListNode* pSlow = pHead->m_pNext;
    if(pSlow == NULL)
        return false;


    ListNode* pFast = pSlow->m_pNext;
    while(pFast != NULL && pSlow != NULL)
    {
        if(pFast == pSlow)
            return true;


        pSlow = pSlow->m_pNext;


        pFast = pFast->m_pNext;
        if(pFast != NULL)
            pFast = pFast->m_pNext;
    }


    return false;
}

Esta solución está disponible en mi blog.Hay un problema más discutido en el blog:¿Cuál es el nodo de entrada cuando hay un ciclo/bucle en una lista?

Solución "Hack" (debería funcionar en C/C++):

  • Recorra la lista y establezca el último bit de next puntero a 1.
  • Si encuentra un elemento con un puntero marcado, devuelva verdadero y el primer elemento del ciclo.
  • Antes de regresar, restablezca los punteros, aunque creo que la desreferenciación funcionará incluso con los punteros marcados.

La complejidad del tiempo es 2n.Parece que no utiliza ninguna variable temporal.

Esta es una solución que utiliza una tabla Hash (en realidad, solo una lista) para guardar la dirección del puntero. 

def hash_cycle(node):
    hashl=[]
    while(node):
        if node in hashl:
            return True
        else:
            hashl.append(node)
            node=node.next
    return False

def has_cycle(cabeza):contador = establecer()

while head is not None:
    if head in counter:
        return True
    else:
        counter.add(head)
        head = head.next
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top