Linked List Cycle

Q: Qual è la complessità temporale e spaziale di Linked List Cycle?

Entrambi gli approcci richiedono un tempo O(n) , poiché ogni nodo viene attraversato un numero limitato di volte. Contrassegnare i nodi visitati richiede O(n) di memoria aggiuntiva. I puntatori veloce e lento di Floyd richiedono O(1) : due numeri di nodo.

Q: Perché il puntatore veloce non può saltare oltre il puntatore lento?

All'interno del ciclo, a ogni iterazione fast avanza di due nodi e slow di uno, quindi la distanza che fast deve ancora percorrere per raggiungere slow diminuisce esattamente di uno. Una distanza che diminuisce di uno a ogni iterazione segue la sequenza 3, 2, 1, 0 e non può diventare negativa, quindi i due puntatori si incontrano su un nodo.

FacilePuntatore veloce e lento Lista concatenata

+10

Una lista concatenata è memorizzata nell'array next: il nodo i punta al nodo next[i] e -1 indica la fine della lista. La testa è il nodo 0. Segui i collegamenti a partire dalla testa e restituisci true se torni a un nodo che hai già visitato, oppure false se raggiungi la fine. I nodi che il percorso non raggiunge non contano, anche se puntano l'uno all'altro formando un ciclo.

Funzione

hasCycle(next: integer-array) → boolean

nextinteger-array: il collegamento di ogni nodo: next[i] è il nodo successivo al nodo i, oppure -1
Restituisceboolean: vero se il percorso dal nodo 0 visita di nuovo un nodo, falso se raggiunge -1

Vincoli

1 ≤ next.length ≤ 10⁴
-1 ≤ next[i] ≤ next.length-1
Diversi nodi possono collegarsi allo stesso nodo e alcuni nodi potrebbero non essere raggiungibili dalla testa.

Esempi

Input: next = [1, 2, 3, 1]
Output: true
Spiegazione: Il percorso procede 0, 1, 2, 3 e poi torna a 1. Il nodo 1 viene visitato due volte, quindi la lista ha un ciclo che passa per i nodi 1, 2 e 3.

Input: next = [2, -1, 1]
Output: false
Spiegazione: Il percorso passa per 0, 2, 1 e poi raggiunge -1: tre nodi diversi e poi la fine, quindi non c'è alcun ciclo.

Input: next = [-1, 2, 1]
Output: false
Spiegazione: Il nodo 0 punta a -1, quindi la lista è lunga un nodo. I nodi 1 e 2 puntano l’uno all’altro formando un ciclo, ma il percorso dalla testa non li raggiunge mai.

+16 test nascosti all’invio

Per approfondire

Riesci anche a trovare il nodo in cui inizia il ciclo, sempre con memoria extra O(1)?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Una lista senza ciclo raggiunge -1 entro n collegamenti, ma una lista con un ciclo non finisce mai, quindi non puoi aspettare che finisca. Ti serve un modo per accorgerti che il percorso si ripete. Ricordare ogni nodo che visiti richiede una memoria O(n). I puntatori veloce e lento di Floyd fanno lo stesso usando due interi, perché un puntatore che si muove a velocità doppia deve raggiungere quello lento all'interno di un ciclo.

Contrassegna i nodi che visiti

Intuizione

Parti dal nodo 0 e contrassegna ogni nodo quando lo lasci. Se arrivi a un nodo già contrassegnato, il percorso è tornato a quel nodo e da lì si ripete all’infinito: è un ciclo. Nell’esempio 1 contrassegni 0, 1, 2 e 3, e il collegamento dal nodo 3 conduce al nodo 1, che è contrassegnato.

I nodi sono numerati da 0 a n-1, quindi un array booleano di lunghezza n funge da insieme dei nodi visitati. In una lista collegata costruita con oggetti, inseriresti invece i riferimenti ai nodi in un insieme hash; l’idea è la stessa.

Ogni nodo viene contrassegnato al massimo una volta e il percorso si ferma alla prima ripetizione o a -1, quindi richiede al massimo n passaggi: tempo O(n) e memoria O(n) per i contrassegni.

Algoritmo

Crea un array booleano visited di lunghezza n, con tutti i valori false.
Imposta node = 0.
Mentre node non è -1, restituisci true se visited[node] è già true.
Altrimenti imposta visited[node] e passa a next[node].
Quando il percorso raggiunge -1, restituisci false.

def hasCycle(next):
    visited = [False] * len(next)
    node = 0
    while node != -1:
        if visited[node]:
            return True  # back at a node already on the path
        visited[node] = True
        node = next[node]
    return False

Puntatori veloci e lenti (rilevamento dei cicli di Floyd)

Intuizione

Fai partire due puntatori dalla testa. slow segue un collegamento per turno e fast ne segue due. Se la lista termina, fast raggiunge per primo -1 e restituisci false. Se c’è un ciclo, fast vi entra per primo e continua a girarci finché non arriva anche slow.

Una volta che entrambi sono nel ciclo, a ogni turno fast guadagna esattamente un nodo su slow. La distanza che fast deve ancora percorrere per raggiungere slow diminuisce di uno a ogni turno, quindi arriva a zero e i puntatori si trovano sullo stesso nodo. Guadagnando un nodo alla volta, fast non può mai saltare oltre slow.

Nell’esempio 1, dopo un turno slow è sul nodo 1 e fast sul nodo 2. Dopo due turni slow è sul nodo 2 e fast ha percorso i nodi 3 e 1. Dopo tre turni entrambi sono sul nodo 3, quindi la risposta è true.

slow ha bisogno al massimo di n turni per entrare nel ciclo e, una volta dentro, i due si incontrano prima che completi un giro, quindi il tempo è O(n). L’unica memoria utilizzata è quella necessaria per due numeri di nodo.

Algoritmo

Imposta slow = 0 e fast = 0.
Mentre fast è diverso da -1 e next[fast] è diverso da -1, sposta slow di un collegamento e fast di due collegamenti.
Dopo ogni spostamento, restituisci true se si trovano sullo stesso nodo.
Quando il ciclo si interrompe, fast ha trovato la fine: restituisci false.

def hasCycle(next):
    slow = 0
    fast = 0
    # fast needs two links to move; if either is missing, the list ends.
    while fast != -1 and next[fast] != -1:
        slow = next[slow]
        fast = next[next[fast]]
        if slow == fast:
            return True
    return False

Trappole e casi limite

Qui i bug riguardano la fine della lista e quali nodi vengono considerati.

Spostare fast di due collegamenti senza effettuare entrambi i controlli. fast e next[fast] devono essere entrambi nodi validi prima di leggere next[next[fast]]; altrimenti si legge next[-1], causando un crash nella maggior parte dei linguaggi e restituendo silenziosamente l'ultimo elemento in Python.
Confrontare i puntatori prima di spostarli. Entrambi partono dal nodo 0, quindi un controllo all'inizio del ciclo segnala un ciclo in ogni lista.
Esaminare l'intero array invece del percorso. In [-1, 2, 1] i nodi 1 e 2 formano un ciclo, ma il percorso dalla testa termina subito, quindi la risposta è false. Anche controllare se un valore si ripete in next è sbagliato: in [4, 4, 4, 4, -1] diversi nodi puntano al nodo 4 e non c'è alcun ciclo.
Supporre che un ciclo debba tornare alla testa. In [1, 2, 3, 4, 4] l'ultimo nodo punta a sé stesso, e in [0] lo fa la testa.

Domande frequenti4

Come funziona il rilevamento dei cicli di Floyd?

Due puntatori partono dalla testa: uno avanza di un collegamento per passo, l'altro di due. Senza un ciclo, quello veloce raggiunge la fine. Con un ciclo, entrambi finiscono al suo interno, quello veloce riduce la distanza di un nodo a ogni passo e si incontrano sullo stesso nodo.

Qual è la complessità temporale e spaziale di Linked List Cycle?

Entrambi gli approcci richiedono un tempo O(n), poiché ogni nodo viene attraversato un numero limitato di volte. Contrassegnare i nodi visitati richiede O(n) di memoria aggiuntiva. I puntatori veloce e lento di Floyd richiedono O(1): due numeri di nodo.

Perché il puntatore veloce non può saltare oltre il puntatore lento?

All'interno del ciclo, a ogni iterazione fast avanza di due nodi e slow di uno, quindi la distanza che fast deve ancora percorrere per raggiungere slow diminuisce esattamente di uno. Una distanza che diminuisce di uno a ogni iterazione segue la sequenza 3, 2, 1, 0 e non può diventare negativa, quindi i due puntatori si incontrano su un nodo.

Riesci a individuare il ciclo contando i passaggi?

In questa forma di array, sì: una lista senza ciclo raggiunge -1 entro n collegamenti, quindi percorrere n collegamenti senza raggiungere la fine dimostra che c'è un ciclo, con memoria O(1). Serve il numero di nodi, che una lista composta da puntatori non fornisce, e contarli prima non termina mai se c'è un ciclo. Il metodo di Floyd non richiede conteggi.

Python

def hasCycle(next):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

next = [1, 2, 3, 1]

Atteso

true