ho sentito una questione intervista:Stampare una lista semplicemente legata al contrario, nello spazio costante e tempo lineare
"stampare un elenco singolarmente legata a ritroso, nello spazio costante e tempo lineare."
La mia soluzione era di invertire la lista collegata sul posto e quindi stamparla in quel modo. C'è un'altra soluzione che non è distruttiva?
Se si inverte nuovamente dopo la stampa non sarà più essere distruttiva, dal momento che l'ordine originale viene ripristinato.
È possibile utilizzare una chiamata ricorsiva nella catena di elenchi collegati con un riferimento a ciò a cui si desidera scrivere. Ogni nodo userebbe la funzione di stampa del nodo figlio mentre passava il riferimento prima di stamparsi.
In questo modo ogni nodo nell'elenco passerebbe in basso, fino a quando l'ultimo non poteva e sarebbe andato direttamente in scrittura, quindi ogni backup della catena avrebbe scritto dopo l'ultimo tutto il ritorno in avanti .
Modifica
Questo in realtà non va bene per le specifiche a causa della spazio lineare sulla pila. Se si dispone di qualcosa all'esterno per eseguire le funzioni e un metodo di scrittura nella parte anteriore di una stringa, la logica di base può comunque funzionare.
Ma quello userebbe lo spazio di stack O (n) =/ –
Quello è lo spazio lineare: la pila conta come spazio. –
@Razor - lol, sei un po 'più veloce sulla tastiera. –
Basta iterare e stamparlo lungo il percorso ma capovolgere il monitor.
˙uoıʇɐɯɹoɟsuɐɹʇ ʇxǝʇ ǝlʇʇıl ɐ ɥʇıʍ ʇɥƃıɹ ʇsoɯlɐ ʞool uɐɔ ʇI
LOL migliore soluzione finora –
Aw man, mi ha battuto per questo. –
Ecco un approccio non convenzionale: cambiare la console in ordine di lettura da destra a sinistra e quindi stampare l'elenco in ordine normale. Appariranno in ordine inverso. Dover visitare i dati effettivi in ordine inverso non sembra un vincolo al problema.
Hai già capito la maggior parte della risposta: rovescia la lista collegata in posizione e attraversa la lista fino all'inizio per stamparla. Per evitare che diventi (permanentemente) distruttivo, rovescia l'elenco collegato in posizione di nuovo mentre lo stai attraversando all'inizio e stampalo.
Nota, tuttavia, questo funziona solo se hai solo un singolo thread di esecuzione, o fai l'intero attraversamento di una sezione critica in modo che solo un thread lo faccia alla volta (cioè, un secondo thread non può mai giocare con la lista nel mezzo della traversata).
Entrambe le prime due risposte rispondono esattamente a questa domanda. Ho scelto l'altro perché è stato pubblicato in precedenza. Ma ho votato questo perché ha più dettagli. Peccato che non mi permetta di accettare più di una risposta se sono molto simili: [ –
Ok, questa potrebbe essere una domanda di intervista, ma in realtà è una domanda dietro il libro degli algoritmi di Weis. La domanda afferma chiaramente che non possiamo usare la ricorsione (qualcosa che l'intervistatore si nasconderà e rivelerà in seguito) poiché la ricorsione non userà lo spazio costante, la ricorsione in miniatura diventerà un importante punto di discusione. La soluzione è invertita e rovesciata.
Questo è quello che stavo pensando. Tuttavia, è una buona pratica in una situazione del mondo reale?(Assumendo passaggio per riferimento) –
In realtà lo si dovrebbe invertire prima senza stampare e quindi stamparlo mentre lo si inverte nuovamente. – x4u
@Razor: ish. Normalmente se si passa qualcosa per la stampa, ci si aspetterebbe che il callee la consideri non modificabile. Quindi, nelle lingue che si preoccupano di questo tipo di cose, la funzione deve (a sorpresa) prendere un parametro non-const oppure la funzione stessa deve contenere codice const-non sicuro. Dovresti decidere se i benefici valgono il rischio aggiuntivo di scrivere codice errato o se sarebbe meglio fare una copia inversa dell'elenco o utilizzare invece una struttura bidirezionale (ad esempio una lista doppiamente collegata). Se è un beneficio abbastanza serio, qualsiasi cosa è una buona pratica ;-) –