número Count de nodos en una lista enlazada que puede ser circular

Aquí está el problema, es a partir excelentes Algoritmos de Sedgwick en Java (q 3,54)número Count de nodos en una lista enlazada que puede ser circular

dado un enlace a un nodo en una lista enlazada que no contiene ningún los enlaces nulos (es decir, cada nodo ya sea enlaces a sí mismo u otro nodo en la lista) determinan el número de nodos diferentes sin modificar ninguno de los nodos y utilizando no más espacio de memoria constante.

¿Cómo lo haces? Examine la lista una vez usando el algoritmo de liebre y tortuga para determinar si es circular de alguna manera, y luego vuelva a explorar para determinar dónde la lista se vuelve circular, luego vuelva a explorar contando el número de nodos en esta posición. Suena un poco brutal para mí, creo que hay una solución mucho más elegante.

Fuente

2009-09-18 Tom

El tortoise and hare algorithm le puede dar tanto la duración del ciclo y el número de nodos antes de que comience el ciclo (λ y Mu respectivamente).

Fuente

2009-09-18 00:52:53 Artelius

Jaja, estaba en el medio de idear una respuesta elaborada en base a mi idea de que el número de pasos que tomaría una tortuga y una liebre para cumplir me da información sobre la duración del ciclo, cuando debería haberlo buscado. – Joren

Yo también. :(Google es mi amigo, Google es mi amigo, Google es mi amigo ... – TonyOssa

+1. ¿Pero cuál es la complejidad de tiempo de su algoritmo? Buscar ciclo O (lambda + u), encontrar longitud de ciclo O (lambda), encuentra la longitud del cuello O (lambda * u). En general sigue siendo O (N^2) suponiendo N = min (lambda, u). ¿Hay una mejor manera que cuadrática? – Akusete

-4

acaba de recordar dónde has estado y si llegaste al mismo nodo se ha terminado.

Intenta almacenar entradas en árbol binario y tiene O (n * log (N)) tiempo y O (N) comlexity espacio

EDITAR

Puede utilizar log (n) el espacio comlexity si no almacene todos los enlaces excepto en el orden exponencial. Eso significa que almacenas 1º, 2º, 4º, 8º, 16º y luego, si te golpean, debes continuar desde ese punto. comlexity Tiempo para éste es N * log (n)^2

Fuente

2009-09-18 00:23:39

pero solo puede usar el espacio constante – Tom

log (N) es espacio casi constante 100 entradas deberían ser suficientes para cada disco/ram en el mundo: D –

@ralu: Lo sentimos, pero 'O (log N)' no está cerca al espacio 'O (1)'. Ni por asomo. – jason

Salida esto: Puzzle: Loop in a Linked List

Pointer Marcado: En la práctica, vinculados listas se implementan utilizando estructuras C con al menos un puntero; tal estructura en C debe estar alineada con 4 bytes. Entonces, los dos bits menos significativos son ceros. Mientras recorre la lista, puede 'marcar' un puntero como atravesado por volteando el bit menos significativo. Un segundo recorrido es para limpiar estos bits .

Fuente

2009-09-18 00:29:15

La pregunta establece que debe "determinar el número de nodos diferentes sin modificar ninguno de los nodos". Incluso si esto no fuera un requisito, esta solución huele porque depende demasiado de un detalle de implementación y no es independiente del idioma. – jason

@Jason: ¿A quién le importa? Prefiero un algoritmo * rápido * (que se adapte a mi entorno) a uno que funcione en más idiomas. No estoy diciendo que esta respuesta describa un algoritmo rápido, solo que, en general, el rendimiento de un algoritmo es más importante que la portabilidad. – Artelius

@Jason, sí modifica temporalmente los nodos. De todos modos, sé que no es la mejor solución, pero creo que es interesante. –

La solución más elegante es el algoritmo ciclo de investigación de Floyd: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

Se ejecuta en tiempo O (N), y sólo se requiere cantidad constante de memoria.

Fuente

2009-09-18 00:55:24

número Count de nodos en una lista enlazada que puede ser circular

Respuesta

Cuestiones relacionadas