algorithm - toda - El mejor algoritmo para probar si una lista vinculada tiene un ciclo

tipos de datos abstractos en java

Question

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

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

[Editar] La pregunta original no se dirigía a los nodos con un grado superior a 1, pero se habla de ello. Esa pregunta está más en la línea de "Mejor algoritmo para detectar ciclos en un gráfico dirigido".

Answer 1

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

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

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

Solo para subrayar mi punto: el coloreado de los vértex se usa para detectar ciclos en dependencias de los recolectores de basura modernos, por lo que hay un caso de uso muy real para él. En su mayoría usan banderas de bits para realizar el coloreado.

Answer 2

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

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

Answer 3

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

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

Answer 4

Condición previa: realice un seguimiento del tamaño de la lista (actualice el tamaño cuando se agrega o elimina 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 también la operación de actualización del tamaño de la lista, debe hacerse a prueba de subprocesos.

Answer 5

Deberá visitar cada nodo para determinar esto. Esto puede hacerse recursivamente. Para evitar que visite nodos ya visitados, necesita una bandera que diga ''ya visitado''. Esto, por supuesto, no te da bucles. Entonces, en lugar de una bandera de bit, usa un número. Comience por 1. Compruebe los nodos conectados y luego márquelos como 2 y repita hasta que la red esté cubierta. Si al verificar los nodos encuentras un nodo que es más de uno menor que el nodo actual, entonces tienes un ciclo. La duración del ciclo viene dada por la diferencia.

Answer 6

Dos punteros se inicializan a la cabeza de la lista. Un puntero se adelanta 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 nuevamente, hay un ciclo en la lista. De lo contrario, no hay ningún bucle si el más rápido alcanza el final de la lista.

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

Answer 7

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

El algoritmo de DrPizza es definitivamente el camino a seguir.

Answer 8

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

Answer 9

Me pregunto si hay alguna otra manera que no sea ir iterativamente: rellenar una matriz mientras avanza, y verificar si el nodo actual ya está presente en la matriz ...

Answer 10

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

• Recorre la lista y establece el último bit del next puntero en 1.
• Si encuentra un elemento con un puntero marcado, devuelva true y el primer elemento del ciclo.
• Antes de volver, reinicie los punteros, aunque creo que la desreferenciación funcionará incluso con punteros marcados.

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

Answer 11

Tener dos punteros iterando a través de la lista; hacer una iteración al doble de velocidad que la otra, y comparar sus posiciones en cada paso. Fuera 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 puedes obtener.

Answer 12

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 apunta al siguiente nodo.

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

condiciones:

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

2) ambos puntero apuntando a nulo: no hay bucle

Answer 13

def has_cycle (head): counter = set ()

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