Detectar o início de um loop em uma lista de links isolados?

https://stackoverflow.com/questions/1536944

20-09-2019
|

Pergunta

Existe alguma maneira de descobrir o início de um loop em uma lista de links usando Não mais de duas dicas?Não quero visitar todos os nós e marcá -lo e relatar o primeiro nó já foi visto. Há alguma outra maneira de fazer isso?

Solução

Eu ouvi essa pergunta exata como uma pergunta de entrevista.

A solução mais elegante é:

Coloque os dois ponteiros no primeiro elemento (chame -os de A e B)

Então continue em loop ::

Avance A para o próximo elemento
Avance A para o próximo elemento novamente
Avance B para o próximo elemento

Toda vez que você atualiza um ponteiro, verifique se A e B são idênticos. Se, em algum momento, os ponteiros A e B são idênticos, você terá um loop. O problema dessa abordagem é que você pode acabar se movendo ao redor do loop duas vezes, mas não mais que duas vezes com o ponteiro a

Se você quer encontrar o elemento que tem duas dicas apontando para ele, isso é mais difícil. Eu saía de um membro e diria que é impossível ver com apenas duas dicas, a menos que você esteja disposto a repetir após a lista vinculada um grande número de vezes.

A maneira mais eficiente de fazer isso com mais memória seria colocar os ponteiros nos elementos e matar, classificá -lo e depois procurar uma repetição.

Outras dicas

Passo 1: Prossiga da maneira usual, você usará para encontrar o loop, ou seja, dois ponteiros, incrementam um em um único passo e outro em duas etapas, se ambas se encontrarem em algum momento, há um loop.

Passo 2: Congelar um ponteiro onde estava e incrementar o outro ponteiro em uma etapa, contando as etapas que você dá e, quando os dois se encontrarem novamente, a contagem lhe dará o comprimento do loop (isso é o mesmo que contando o número de elementos em um link circular Lista).

Etapa 3: Redefina os dois ponteiros para o início da lista de links, incrementam um ponteiro para o comprimento dos tempos de loop e inicie o segundo ponteiro. incremento ambos os ponteiros em uma etapa e quando se encontrarem novamente, será o começo do loop (este é o mesmo que encontrar o n^º elemento do final da lista de links).

Prova matemática + a solução

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 simples: quando k <n

Quando P mudaria de Beginloop para Meetpont, ele teria percorrido as etapas 'MK'. Nesse período, Q teria percorrido as etapas '2 (MK). Mas, desde que eles se conheceram, e Q começou a 'nk', passos atrás do Beginloop, então, efetivamente, '2 (mk) - (nk)' deve ser igual a '(mk)' então,

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

Isso significa que P e Q se encontram no ponto igual ao número de etapas (ou múltiplas para serem gerais, veja o caso mencionado abaixo) no loop. Agora, no encontro, p e q estão 'n- (mk)' passos atrás, ou seja, 'k' passos atrás, como vimos n = m. Portanto, se iniciarmos P do cabeçalho novamente, e Q do encontro, mas desta vez com o ritmo igual a P, P e Q agora se reunirão apenas no Beginloop.

Caso geral: digamos, k = nx + y, y <n(Daí, k%n = y)

Quando o ponteiro 'P' estaria em Beginloop (ou seja, teria percorrido as etapas 'K'), Q teria percorrido as etapas de '2k'. Portanto, efetivamente, q está à frente de '2k-k = k' etapas de p quando p entra no loop. Mas, por favor, observe que 'k' é maior que 'n', o que significa que Q teria feito várias rodadas do loop. Portanto, efetivamente, Q é os passos 'n- (k%n) atrás do Beginloop agora.

Quando P teria mudado de Beginloop para o MeetPoint, ele teria percorrido as etapas 'MK'. (Portanto, efetivamente, o MeetPoint estaria em '(mk)%n' passos à frente de Beginloop agora.) Nesse período, Q teria viajado '2 (MK)'. Mas, desde que eles se conheceram, e Q iniciou os passos 'n- (k%n)' atrás do Beginloop, então, efetivamente, nova posição de Q (que é '(2 (Mk) - (nk/%n))%n 'de Beginloop) deve ser igual à nova posição de p (que é' (mk)%n 'do loop de início).

Então,

=> (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'

Primeiro, tentamos descobrir, existe algum loop na lista ou não. Se existir loop, tentamos descobrir o ponto de partida do loop. Para isso, usamos dois ponteiros, como lenta e fastptr. Na primeira detecção (verificando o loop), o FastPtr move duas etapas de uma só vez, mas o SlowPTR se move em um passo à frente de uma só vez.

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

É claro que, se houver algum loop na lista, eles se reunirão no ponto (ponto 7 na imagem acima), porque o ponteiro FastPtr está funcionando duas vezes mais rápido que o outro.

Agora, chegamos ao segundo problema de encontrar o ponto de partida do loop.

Suponha que eles se encontrem no ponto 7 (como mencionado na imagem acima). Em seguida, o SlowPTR sai do loop e fica no início da lista significa no ponto 1, mas o FastPtr ainda no ponto de encontro (ponto 7). Agora, comparamos o valor dos dois ponteiros, se eles mesmos, o ponto de partida do loop, caso contrário, movemos uma etapa para a frente (aqui o FastPtr também está se movendo uma etapa a cada vez) e comparamos novamente até encontrarmos o mesmo ponto.

slowPtr   1   2   3   4
fastPtr   7   8   9   4

Agora vem uma pergunta, como é possível. Portanto, há uma boa prova matemática.

Suponha:

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.

Mais detalhes aqui

Prossiga da maneira usual que você usará para encontrar o loop. ou seja. Tenha duas dicas, o incremento um em uma etapa única (slowpointer) e outras em duas etapas (FastPointer), se ambas se encontrarem em algum momento, haverá um loop.

Como você já teria percebido que o ponto de encontro é K passo antes do chefe do loop.

onde K tem o tamanho da parte não loopada da lista.

Agora mova lentamente para a cabeça do loop

Mantenha rápido no ponto de colisão

Cada um deles é K passo desde o início do loop (lento desde o início da lista, onde o mais rápido é K, o passo antes da cabeça do loop- desenhe a foto para obter a clareza)

Agora mova -os na mesma velocidade - eles devem se encontrar no Loop Start

por exemplo

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

Este é o código para encontrar o início do loop na lista vinculada:

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);
}

Existem duas maneiras de encontrar os loops em uma lista de links. 1. Use dois ponteiros um avanço uma etapa e outro avanço duas etapas Se houver loop, em algum momento ambos os ponteiros obtêm o mesmo valor e nunca atingem o NULL. Mas se não houver um ponteiro de loop atingir o NULL em um ponto e ambos os ponteiros nunca obterão o mesmo valor. Mas, nessa abordagem, podemos chegar lá, há um loop na lista de links, mas não podemos dizer onde exatamente inicia o loop. Esta não é a maneira eficiente também.

Use uma função de hash de tal maneira que o valor deve ser único. Caso se estivermos tentando inserir o duplicado, deve -se através da exceção. Em seguida, viaje por cada nó e empurre o endereço para o hash. Se o ponteiro chegar a NULL e nenhuma exceção do hash significa que não há ciclo na lista de links. Se estamos obtendo alguma exceção do hash significa que há um ciclo na lista e esse é o link do qual o ciclo está começando.

Bem, eu tentei de uma maneira usando um ponteiro ... tentei o método em vários conjuntos de dados .... como a memória para cada um dos nós de uma lista vinculada são alocados em uma ordem crescente; portanto, enquanto atravessa a lista vinculada de A cabeça da lista vinculada, se o endereço de um nó se tornar maior que o endereço do nó para o qual estiver apontando, podemos determinar que existe um loop, bem como o elemento inicial do loop.

A melhor resposta que encontrei foi aqui:
TianRunhe: Find-loop iniciar uma lista ligada ao circular

'm' sendo distância entre a cabeça e start_loop
'L' sendo o comprimento do loop
'd' sendo distância entre meeting_point e start_loop
P1 movendo -se em V e P2 movendo -se a 2*V

Quando os 2 ponteiros se encontram: a distância é = m+ n*l -d = 2*(m+ l -d)
=> O que significa (não a matemática demonstrou aqui) que se o P1 começar do Head & P2 começar em Meeting_Point e eles se movem no mesmo ritmo, eles se encontrarão @ start_loop

Referir-se isto Link para uma resposta abrangente.

Prossiga da maneira usual que você usará para encontrar o loop. ou seja. Tenha duas dicas, o incremento um em um único passo e outro em duas etapas, se ambas se encontrarem em algum momento, há um loop.
Mantenha um dos ponteiros corrigidos, obtenha o número total de nós no loop diz L.
Agora, a partir deste ponto (incremento o segundo ponteiro para o próximo nó no loop) no loop revertem a lista vinculada e conte o número de nós atravessados, digamos x.
Agora, usando o segundo ponteiro (o loop está quebrado) do mesmo ponto no loop travrse a lista vinculada e conte o número de nós restantes, digamos y
O loop começa após os nós ((x+y) -l) 2. Ou começa no (((x+y) -l) 2+1) o nó.

Prossiga da maneira usual que você usará para encontrar o loop. ou seja. Tenha duas dicas, o incremento um em um único passo e outro em duas etapas, se ambas se encontrarem em algum momento, há um loop.
Mantenha um dos ponteiros corrigidos, obtenha o número total de nós no loop diz L.
Agora, a partir deste ponto (incremento o segundo ponteiro para o próximo nó no loop) no loop revertem a lista vinculada e conte o número de nós atravessados, digamos x.
Agora, usando o segundo ponteiro (o loop está quebrado) do mesmo ponto no loop travrse a lista vinculada e conte o número de nós restantes, digamos y
O loop começa após os nós ((x+y) -l) 2. Ou começa no (((x+y) -l) 2+1) o nó.

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);
}

detectar loop
Copie o endereço de cada elemento no conjunto. Se a duplicata for encontrada, é o início do loop

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow