Mejor algoritmo para probar si una lista enlazada tiene un ciclo

Condición previa: Mantenga un registro del tamaño de la lista (actualice el tamaño cuando se agregue o elimine un nodo).

Detección de bucle:

1. Mantenga un contador cuando atraviese el tamaño de la lista.

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

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 del tamaño de la lista, deben ser seguras para el hilo.

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

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

2) el puntero q irá cada vez solo en dirección hacia adelante.

Condiciones:

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

2) ambos puntero apuntando a null: no hay bucle

¿Qué hay de usar una tabla hash para almacenar los nodos ya vistos (los observa en orden desde el comienzo de la lista)? En la práctica, se podría lograr algo cercano a O (N).

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

Me pregunto si hay alguna otra manera que simplemente ir iterativamente - rellenar una matriz a medida que avanza, y comprobar 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 hace como máximo dos pasadas a través de la lista (si el último nodo está vinculado a la penúltima lode), y en el caso común (sin bucle) hará solo una pasada. 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 hace como máximo dos pasadas a través de la lista (si el último nodo está vinculado a la penúltima lode), y en el caso común (sin bucle) hará solo una pasada. Sin hash, sin asignación de memoria, etc.

Sí. He notado que la formulación no era perfecta y la he reformulado. Todavía creo que un hachís inteligente podría funcionar más rápido-por un pelo. Creo que su algoritmo es la mejor solución, sin embargo.

Solo para subrayar mi punto: la coloración vertec se usa para detectar ciclos en dependencias por los recolectores de basura modernos, por lo que hay 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 recursivamente. Para evitar que visites nodos ya visitados, necesitas un indicador que diga 'ya visitado'. Esto, por supuesto, no te da bucles. Así que en lugar de una bandera de bits, utilice un número. Empieza a la 1. Compruebe los nodos conectados y luego márquelos como 2 y recurra hasta que la red esté cubierta. Si al comprobar nodos se encuentra con 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.

Dos punteros se inicializan 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 se encuentra con el más lento de nuevo, hay un bucle en la lista. De lo contrario no hay bucle si el más rápido llega al final de la lista.

El siguiente código de ejemplo 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 ciclo / bucle en una lista?

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

• Recorre la lista y establece el último bit del puntero next en 1.
• If find an element with flagged pointer return return true y el primer elemento del ciclo.
• Antes de regresar, restablezca los punteros, aunque creo que la desreferenciación funcionará incluso con punteros marcados.

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

Esta es una solución que utiliza una tabla Hash ( solo una lista en realidad) 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): counter = set ()

while head is not None:
    if head in counter:
        return True
    else:
        counter.add(head)
        head = head.next