numero conte di nodi in una lista collegata che può essere circolare

Qui è il problema, è da eccellenti algoritmi di Sedgwick in Java (q 3,54)numero conte di nodi in una lista collegata che può essere circolare

Dato un link a un nodo in una lista concatenata semplice che non contiene i collegamenti nulli (ovvero ogni nodo si collega a se stesso o ad un altro nodo nell'elenco) determinano il numero di nodi diversi senza modificare nessuno dei nodi e non utilizzano più di uno spazio di memoria costante.

Come si fa? scansiona l'elenco una volta usando l'algoritmo di lepre e tartaruga per capire se è circolare in qualche modo, quindi eseguire nuovamente la scansione per capire dove l'elenco diventa circolare, quindi eseguire nuovamente la scansione contando il numero di nodi in questa posizione? mi sembra un po 'bruta, immagino ci sia una soluzione molto più elegante.

fonte

2009-09-18 Tom

Il tortoise and hare algorithm può dare sia la lunghezza del ciclo e il numero di nodi prima del ciclo (λ e u rispettivamente).

fonte

2009-09-18 00:52:53 Artelius

Haha, ero nel bel mezzo di elaborare una risposta elaborata basata sulla mia intuizione che il numero di passi necessari per una tartaruga e una lepre per incontrarsi fornisce informazioni sulla durata del ciclo, quando avrei dovuto semplicemente cercarlo. – Joren

Anch'io. :(Google è mio amico, Google è mio amico, Google è mio amico ... – TonyOssa

+1. Ma qual è la complessità temporale del tuo algoritmo? Trova il ciclo O (lambda + u), trova la lunghezza del ciclo O (lambda), trova la lunghezza del collo O (lambda * u) .In generale è ancora O (N^2) assumendo N = min (lambda, u). C'è un modo migliore del quadratico? – Akusete

-4

basta ricordare dove sei stato e se sei arrivato allo stesso nodo è finito.

Prova memorizzare le voci in albero binario e si dispone di O (N * log (N)) tempo e O (N) spazio comlexity

EDIT

È possibile utilizzare log (n) spazio comlexity se non memorizzare tutti i link tranne quelli in ordine esponenziale. Ciò significa che memorizzi 1 °, 2 °, 4 °, 8 °, 16 ° e poi se vieni colpito devi continuare da quel punto. comlexity tempo per questo è N * log (N)^2

fonte

2009-09-18 00:23:39

ma è possibile utilizzare solo lo spazio costante – Tom

log (N) è quasi costante spazio 100 voci dovrebbero essere sufficienti per ogni disco/ram nel mondo: D –

@ralu: scusa, ma 'O (log N)' non è chiuso nello spazio 'O (1)'. Non da un colpo lungo. – jason

Dai un'occhiata a questo: Puzzle: Loop in a Linked List

Pointer Marcatura: In pratica, legati liste sono implementate utilizzando le strutture C con almeno un puntatore; tale struttura in C deve essere allineata a 4 byte. Quindi i due bit meno significativi dello sono zero. Mentre si attraversa l'elenco, è possibile "contrassegnare" un indicatore come indicato da sfogliando il bit meno significativo. Un secondo traversal consente di cancellare questi bit .

fonte

2009-09-18 00:29:15

La domanda indica che è necessario "determinare il numero di nodi diversi senza modificare alcun nodo". Anche se questo non fosse un requisito, questa soluzione odora perché si basa troppo su un dettaglio di implementazione e non è indipendente dal linguaggio. – jason

@ Jason: a chi importa? Preferirei un algoritmo * veloce * (che si adatta al mio ambiente) a uno che funzioni in più lingue. Non sto dicendo che questa risposta descrive un algoritmo veloce, solo che in generale, le prestazioni di un algoritmo sono più importanti della portabilità. – Artelius

@Jason, sì modifica temporaneamente i nodi. Ad ogni modo, so che non è la soluzione migliore, ma penso che sia interessante. –

La soluzione più elegante è Floyd ciclo-algoritmo di ricerca: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

Viene eseguito in O (n), ed è necessaria solo quantità costante di memoria.

fonte

2009-09-18 00:55:24

numero conte di nodi in una lista collegata che può essere circolare

risposta

Problemi correlati