Cracking the Coding Interview, 6th edition, 2.8

Question

Dichiarazione di problema: Dato un elenco circolare collegato, implementare un algoritmo che restituisce il nodo all'inizio del ciclo.

La chiave di risposta fornisce una soluzione più complicata di quella che propongo. Cosa c'è di sbagliato con la mia ?:

public static Node loopDetection(Node n1) { 
    ArrayList<Node> nodeStorage = new ArrayList<Node>(); 

    while (n1.next != null) { 
     nodeStorage.add(n1); 
     if (nodeStorage.contains(n1.next)) { 
      return n1; 
     } 
     else { 
      n1 = n1.next; 
     } 
    } 

    return null; 
} 

Answer 1

tua soluzione è O(n^2) tempo (ogni in ArrayList è O(n) tempo) e O(n) spazio (per la memorizzazione nodeStorage), mentre la soluzione "più complicato" è O(n) tempo e O(1) spazio.

Il libro offre la seguente soluzione, a chi è interessato, che è O(n) tempo e O(1) spazio:

Se ci spostiamo due puntatori, uno con la velocità 1 e un altro con velocità 2, finiranno incontro se l'elenco collegato ha un ciclo. Perché? Pensa a a proposito di due auto che guidano su una pista: l'auto più veloce passerà sempre quella più lenta ! La parte difficile qui è trovare l'inizio del ciclo. Immaginate, come un'analogia, due persone che corrono su una pista, una con lo due volte più veloce dell'altro. Se iniziano allo stesso posto, quando si incontreranno il ? Si incontreranno di nuovo all'inizio del prossimo giro. Ora, supponiamo che Fast Runner abbia un vantaggio di k metri su un giro di prova n . Quando si incontreranno di nuovo? Si incontreranno k metri prima dello inizio del prossimo giro. (Perché? Fast Runner avrebbe realizzato i passaggi di k + 2 (n - k) , incluso il suo start iniziale, e Slow Runner avrebbe eseguito n - k passaggi. Entrambi saranno k passi prima dell'inizio del ciclo.) Ora , passando al , quando Fast Runner (n2) e Slow Runner (n1) sono spostandosi nella nostra lista circolare circolare, n2 avvierà un vantaggio sul ciclo quando n1 entra. In particolare, avrà un vantaggio di k, dove k è il numero di nodi prima del ciclo. Poiché n2 ha un inizio di testa di nodi k , n1 e n2 incontreranno nodi k prima dell'inizio del ciclo . Quindi, ora sappiamo quanto segue: 1. Testa è k nodi da LoopStart (per definizione). 2. MeetingPoint per n1 e n2 è k nodi da LoopStart (come mostrato sopra). Quindi, se spostiamo n1 di nuovo a Capo e mantieni n2 a MeetingPoint, e li sposiamo entrambi allo stesso ritmo, si incontreranno a LoopStart.

LinkedListNode FindBeginning(LinkedListNode head) { 
    LinkedListNode n1 = head; 
    LinkedListNode n2 = head; 

    // Find meeting point 
    while (n2.next != null) { 
     n1 = n1.next; 
     n2 = n2.next.next; 
     if (n1 == n2) { 
     break; 
     } 
    } 
// Error check - there is no meeting point, and therefore no loop 
    if (n2.next == null) { 
     return null; 
    } 
    /* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps 
    /* from the Loop Start. If they move at the same pace, they must 
    * meet at Loop Start. */ 
    n1 = head; 
    while (n1 != n2) { 
     n1 = n1.next; 
     n2 = n2.next; 
    } 
    // Now n2 points to the start of the loop. 
    return n2; 
    } 

Answer 2

V'è la soluzione data da Amit. Il problema è che lo conosci o non lo fai, ma non sarai in grado di capirlo in un'intervista. Dal momento che ho mai ho avuto bisogno di trovare un ciclo in una lista collegata, sapendo che per me è inutile, tranne per il passaggio di interviste. Quindi, per un intervistatore, affermare questo come una domanda di intervista e aspettarsi la risposta dell'amir (che è bello perché ha un tempo lineare e zero spazi extra), è abbastanza stupido.

Quindi la soluzione è per lo più soddisfacente, tranne che è necessario utilizzare una tabella hash e assicurarsi che la hash tabella hash riferimenti ai nodi e non ai nodi. Supponiamo che tu abbia un nodo contenente una stringa e un puntatore "successivo", e la funzione di hash blocca la stringa e confronta i nodi come uguali se le stringhe sono uguali. In quel caso troverai il primo nodo con una stringa duplicata e non il nodo all'inizio del ciclo, a meno che tu non stia attento.

(la soluzione di amir ha un problema molto simile nelle lingue in cui == confronta gli oggetti e non i riferimenti. Ad esempio in Swift, dovresti usare === (confronta i riferimenti) e non == (confronta oggetti)).