15 junio 2007

Solución: Lista enlazada

Esta es la solución al problema del otro día.

Si la lista tiene punteros al elemento anterior, hay varias soluciones, pero si sólo hay punteros a "siguiente" creo que sólo hay una posible y es esta:

Inicialmente los 2 punteros apuntan al primer y segundo elemento de la lista. Entonces dentro de un bucle infinito vamos moviendo un puntero de uno en uno y el otro de dos en dos mirando si apuntan al mismo elemento.

El puntero que va de 2 en 2 llegará en la mitad de tiempo al final (si existe).

Si hay un bucle se pondrá a dar vueltas dentro de él, en algún momento el puntero lento llegará al bucle y en una o dos vueltas coincidirán.

En código creo es algo así, no lo he probado:

pLento = raiz
pRapido = raiz.siguiente
while (1) {
if (pLento == pRapido) {
printf("Tiene un bucle");
return 0;
}

if (pRapido == NULL) {
printf("Es finita");
return 0;
}

if (pRapido.siguiente != NULL)
pRapido = pRapido.siguiente.siguiente;
else
pRapido = pRapido.siguiente;
pLento = pLento.siguiente;
}