rilevare l'inizio di un ciclo in un elenco di link singolarmente concatenata?

Question

C'è un modo di scoprire l'inizio di un ciclo in un elenco di link utilizzando non più di due puntatori? Non voglio visitare ogni nodo e segnare visto e segnalato la primo nodo già stati seen.Is C'è un altro modo per fare questo?

Answer 1

Ho sentito questa domanda esatta come questione intervista quiz.

La soluzione più elegante è:

Mettere entrambi i puntatori al primo elemento (chiamarli A e B)

Quindi tenere loop ::

    
• Advance Un all'elemento successivo     
• Advance Un all'elemento successivo di nuovo     
• Advance B all'elemento successivo

Ogni volta che si aggiorna un puntatore, controllare se A e B sono identici. Se a un certo punto puntatori A e B sono identici, allora avete un ciclo. Problema di questo approccio è che si può finire per muoversi intorno al ciclo due volte, ma non più di due volte con puntatore A

Se si vuole trovare in realtà l'elemento che ha due puntatori che puntano ad esso, che è più difficile. Mi piacerebbe andare fuori di un arto e dire la sua impossibile da fare con solo due puntatori a meno che non si è disposti a ripetere in seguito alla lista collegata di un gran numero di volte.

Il modo più efficace di farlo con più memoria, sarebbe quello di mettere i puntatori agli elementi di matrice e, ordinare, e poi cercare di ripetere.

Answer 2

Step1: , procedere nel modo consueto, verrà utilizzato per trovare il ciclo, vale a dire Avere due puntatori, incrementare uno in unico passaggio e l'altro in due fasi, se entrambi si incontrano a volte, v'è un ciclo.

Fase 2: Blocca un puntatore dove era e incrementare l'altro puntatore in un unico passaggio contando i passi che fate e quando entrambi incontrano di nuovo, il conteggio vi darà la lunghezza del loop (questo è uguale a contare il numero di elementi in una lista di collegamento circolare).

Fase 3: Ripristina entrambi i puntatori per l'inizio della lista di link, incrementare un puntatore alla lunghezza dei tempi di ciclo e quindi avviare il secondo puntatore. incrementare entrambi i puntatori in un unico passaggio e quando si incontrano di nuovo, sarà l'inizio del ciclo (questo è lo stesso come trovare il n ^th elemento dalla fine della lista link).

Answer 3

prova matematica + LA SOLUZIONE

Let 'k' be the number of steps from HEADER to BEGINLOOP.
Let 'm' be the number of steps from HEADER to MEETPOINT.
Let 'n' be the number of steps in the loop.
Also, consider two pointers 'P' and 'Q'. Q having 2x speed than P.

caso semplice: Quando k

Quando l'indicatore 'P' sarebbe a BEGINLOOP (cioè esso avrebbe viaggiato passi 'k'), Q avrebbe viaggiato passi '2k. Così, in modo efficace, Q è davanti a gradini '2k-k = k' da P quando P entra nel ciclo, e quindi, Q è 'n-k' passi dietro la BEGINLOOP ora.

Quando P si sarebbe mosso da BEGINLOOP a MEETPONT, avrebbe viaggiato passi 'm-k'. In quel tempo, Q avrebbe viaggiato '2 (m-K)' passi. Ma, dal momento che si sono incontrati, e Q hanno iniziato 'n-k' passi dietro la BEGINLOOP, così, in modo efficace, '2 (m-k) - (n-k)' deve essere uguale a '(m-k)' Così,

=> 2m - 2k - n + k = m - k
=> 2m - n = m
=> n = m

significa, P e Q si incontrano nel punto uguale al numero di passi (o multipli di essere generale, vedere il caso di cui sotto) nel ciclo. Ora, alla MEETPOINT, sia P e Q sono 'N- (m-k)' passi indietro, cioè, passi 'k' dietro, come abbiamo visto n = m. Quindi, se si parte da P HEADER nuovo, e Q dal MEETPOINT ma questa volta con il ritmo pari a P, P e Q sarà ora incontro presso BEGINLOOP solo.

Caso generale: Say, k = nX + Y, Y (Quindi, k% n = Y)

Quando l'indicatore 'P' sarebbe a BEGINLOOP (cioè esso avrebbe viaggiato passi 'k'), Q avrebbe viaggiato passi '2k. Così, in modo efficace, Q è davanti a gradini '2k-k = k' da P quando P entra nel ciclo. Ma, si prega di notare 'k' è maggiore di 'n', il che significa che Q avrebbe fatto vari cicli di loop. Così, in modo efficace, Q è 'n- (k% n)' passi dietro la BEGINLOOP ora.

Quando P si sarebbe mosso da BEGINLOOP a MEETPOINT, avrebbe viaggiato passi 'm-k'. (Quindi, efficace, MEETPOINT sarebbe a '(m-k)% n' passi avanti BEGINLOOP ora). In quel momento, Q avrebbe viaggiato '2 (m-k)' passi. Ma, dal momento che si sono incontrati, e Q hanno iniziato 'n- (k% n)' passi dietro la BEGINLOOP, così, in modo efficace, nuova posizione di Q (che è '(2 (Mc) - (NK /% n))% n 'da BEGINLOOP) deve essere uguale alla nuova posizione di P (che è '(mk)% n' da BEGIN LOOP).

=> (2(m - k) - (n - k%n))%n = (m - k)%n
=> (2(m - k) - (n - k%n))%n = m%n - k%n
=> (2(m - k) - (n - Y))%n = m%n - Y   (as k%n = Y)
=> 2m%n - 2k%n - n%n + Y%n = m%n - Y
=> 2m%n - Y - 0 + Y = m%n - Y    (Y%n = Y as Y < n)
=> m%n = 0
=> 'm' should be multiple of 'n'

Answer 4

Prima di tutto cerchiamo di scoprire, c'è qualche ciclo in lista oppure no. Se ciclo esiste allora cerchiamo di scoprire il punto di partenza del ciclo. Per questo usiamo due puntatori e cioè slowPtr e fastPtr. In primo rilevamento (controllo per ciclo), fastPtr muove due passaggi contemporaneamente ma slowPtr muove un passo avanti in una volta.

slowPtr   1   2   3   4   5   6   7
fastPtr   1   3   5   7   9   5   7

E 'chiaro che se c'è qualche ciclo in lista poi si incontrano al punto (punto 7 immagine sopra a), perché puntatore fastPtr è in esecuzione due volte più velocemente di un altro.

Ora, veniamo al secondo problema di trovare punto di partenza del ciclo.

Supponiamo, si incontrano al punto 7 (come indicato in immagine sopra). Poi, slowPtr esce ciclo e si attesta a inizio lista significa al punto 1, ma fastPtr ancora al punto di incontro (punto 7). Ora confrontiamo entrambi Valore di puntatori, se lo stesso allora è punto di partenza del ciclo altrimenti ci muoviamo un passo alla avanti (qui fastPtr è anche in movimento di un passo alla volta) e confrontare di nuovo fino a quando troviamo allo stesso punto.

slowPtr   1   2   3   4
fastPtr   7   8   9   4

Ora, una domanda viene in mente, come è possibile. Quindi v'è una buona dimostrazione matematica.

Supponiamo che:

m => length from starting of list to starting of loop (i.e 1-2-3-4)
l => length of loop (i.e. 4-5-6-7-8-9)
k => length between starting of loop to meeting point (i.e. 4-5-6-7)

Total distance traveled by slowPtr = m + p(l) +k
where p => number of repetition of circle covered by slowPtr

Total distance traveled by fastPtr = m + q(l) + k
where q => number of repetition of circle covered by fastPtr

Since,
fastPtr running twice faster than slowPtr

Hence,
Total distance traveled by fastPtr = 2 X Total distance traveled by slowPtr
i.e
m + q(l) + k = 2 * ( m + p(l) +k )
or, m + k = q(l) - p(l)
or, m + k = (q-p) l
or, m = (q-p) l - k

So,
If slowPtr starts from beginning of list and travels "m" length then, it will reach to Point 4 (i.e. 1-2-3-4)

and
fastPtr start from Point 7 and travels " (q-p) l - k " length then, it will reach to Point 4 (i.e. 7-8-9-4),
because "(q-p) l" is a complete circle length with " (q-p) " times.

Altro dettaglio qui

Answer 5

Procedere nel solito modo si intende utilizzare per trovare il loop. vale a dire. Avere due puntatori, incrementare uno in unico passaggio (slowPointer) e altre in due fasi (fastPointer), Se entrambi si incontrano a volte, v'è un ciclo.

Come forse sarebbe già capito che il punto d'incontro è K Passo prima che la testa del ciclo.

dove k è la dimensione della parte non cappio dell'elenco.

ora passare lento a capo del ciclo

tenere veloce al punto di collisione

ognuno di essi sono k passo fin dall'inizio del ciclo (lento dall'inizio della lista in cui come veloce è passo k prima che la testa del loop-disegnare il pic per ottenere la chiarezza)

Ora spostarli alla stessa velocità - Esse devono rientrare in Loop Start

es

slow=head
while (slow!=fast)
{
     slow=slow.next;
     fast=fast.next;
}

Answer 6

Questo è il codice per trovare all'inizio del ciclo in lista collegata:

public static void findStartOfLoop(Node n) {

    Node fast, slow;
    fast = slow = n;
    do {
        fast = fast.next.next;
        slow = slow.next;
    } while (fast != slow);       

    fast = n;
    do {
        fast = fast.next;
        slow = slow.next;
    }while (fast != slow);

    System.out.println(" Start of Loop : " + fast.v);
}

Answer 7

Ci sono due modi per trovare i loop in un elenco di link. 1. Utilizzare due puntatori un anticipo un passo e altri anticipo due passaggi se c'è loop, in qualche punto sia puntatore ottenere lo stesso valore e non raggiungono mai a nulla. Ma se non c'è puntatore ciclo arriva a zero in un punto ed entrambi puntatore non arrivano mai lo stesso valore. Ma in questo approccio possiamo arrivarci è un ciclo nella lista di link, ma non possiamo dire dove esattamente l'avvio del ciclo. Questo non è il modo efficiente pure.

2. Utilizzare una funzione di hash in modo tale che il valore deve essere univoco. Incase se stiamo cercando di inserire il duplicato dovrebbe attraverso l'eccezione. Poi viaggio attraverso ogni nodo e spingere l'indirizzo nel hash. Se la portata puntatore a NULL e non fa eccezione dal hash significa che non c'è nessun ciclo nella lista di collegamento. Se stiamo ottenendo alcuna eccezione da hash significa che c'è un ciclo nella lista e che è il link da cui il ciclo sta cominciando.

Answer 8

Beh ho cercato un modo utilizzando un puntatore ... Ho provato il metodo in diversi insiemi di dati .... Come la memoria per ciascuno dei nodi di una lista collegata sono allocati in un ordine crescente, così durante l'attraversamento del lista collegata dalla testa della lista collegata, se l'indirizzo di un nodo diventa più grande l'indirizzo del nodo che sta puntando, possiamo determinare c'è un loop, nonché l'elemento all'inizio del ciclo.

Answer 9

La risposta migliore che ho trovato è stato qui:
tianrunhe: Trova- loop-punto di partenza-in-a-circolare liste concatenate

• 'm' essere la distanza tra testa e START_LOOP
• 'L' essere lunghezza del loop
• 'd' essere distanza tra MEETING_POINT e START_LOOP

• p1 muove a V, e p2 muove a 2 * V   

  quando il 2 puntatori si incontrano: distanza percorsa è = m + n * L -d = 2 * (m + L -d)   

    => Che significa (non mathematicaly dimostrato qui) che se p1 parte da TESTA E p2 parte da MEETING_POINT e si muovono alla stessa velocità, si incontreranno @ START_LOOP

Answer 10

Fare riferimento a questo link per risposta esauriente.

Answer 11

1. Procedere nel solito modo si intende utilizzare per trovare il loop. vale a dire. Avere due puntatori, incrementare uno in unico passaggio e l'altro in due fasi, se entrambi si incontrano a volte, v'è un ciclo.

2. Mantenere uno dei puntatori fissato ottenere il numero totale di nodi nel ciclo dire L.

3. Ora da questo punto (incrementa secondo puntatore al nodo successivo nel loop) nel ciclo invertire la lista collegata e contare il numero di nodi attraversati, diciamo X.

4. Ora utilizzando il secondo puntatore (anello è rotto) dallo stesso punto del circuito travrse l'elenco collegato e contare il numero di nodi rimanenti dire Y

5. Il ciclo inizia dopo il (-L (X + Y)) \ 2 nodi. Oppure inizia a (((X + Y) -L) \ 2 + 1) esimo nodo.

Answer 12

1. Procedere nel solito modo si intende utilizzare per trovare il loop. vale a dire. Avere due puntatori, incrementare uno in unico passaggio e l'altro in due fasi, se entrambi si incontrano a volte, v'è un ciclo.

2. Mantenere uno dei puntatori fissato ottenere il numero totale di nodi nel ciclo dire L.

3. Ora da questo punto (incrementa secondo puntatore al nodo successivo nel loop) nel ciclo invertire la lista collegata e contare il numero di nodi attraversati, diciamo X.

4. Ora utilizzando il secondo puntatore (anello è rotto) dallo stesso punto del circuito travrse l'elenco collegato e contare il numero di nodi rimanenti dire Y

5. Il ciclo inizia dopo il (-L (X + Y)) \ 2 nodi. Oppure inizia a (((X + Y) -L) \ 2 + 1) esimo nodo.

Answer 13

void loopstartpoint(Node head){
    Node slow = head.next;;
    Node fast = head.next.next;

    while(fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;

        if(slow==fast){
            System.out.println("Detected loop ");
            break;
        }
    }

    slow=head;
    while(slow!=fast){
        slow= slow.next;
        fast = fast.next;
    }
    System.out.println("Starting position of loop is "+slow.data);
}

Answer 14

1. rilevare ciclo
2. copiare l'indirizzo di ciascun elemento nella serie. Se viene trovato duplicato che è l'inizio del ciclo