Dowód wykrycia początku cyklu w liście połączonej [duplikat]

Jeśli reprezentujesz listę za pomocą wskaźnika do jej pierwszego węzła (list)

Algorytm wykrywania pętli jest opisany następująco:

1. Zadeklaruj Dwa wskaźniki ( pFast) i (pSlow).
2. Make pSlow and pFast point to list.
3. Until ( pSlow), (pFast) lub oba wskazują na NULL:
   1. 
   2. 
   3. If , then STOP as a loop has just been znaleziono.
4. Jeśli ten punkt został osiągnięty (jeden lub oba wskaźniki są NULL), to nie ma pętli na liście.

Przyjmijmy, że algorytm ten jest poprawny. W tym schemacie sytuacja pętli jest reprezentowana przez następujący diagram:

Zauważ, jak każdy węzeł, z wyjątkiem tego wskazującego na początek pętli, jest oznaczony liczbą jego celu minus jeden. Jeśli więc jeden węzeł jest oznaczony i i nie jest początkiem pętli, następnie jest wskazywany jako następny element przez węzeł oznaczony symbolem i-1 .

Algorytm opisany powyżej może być opisany jako pętla, ponieważ jego główny krok (3) jest zbiorem pod-kroków, które powtarzają się do momentu spełnienia warunku wyjścia. To zmusza nas do reprezentowania pFast i pSlow w funkcji numeru iteracji w wykonaniu algorytmu (t ).

Gdyby lista nie miała pętli, pozycje wskaźników byłyby opisane w funkcja t jako:

Istnieje jednak węzeł, w którym zaczyna się pętla i ta funkcja kończy opisując ewolucję wskaźników. Zakładając, że wskaźnik ten jest oznaczony m , że pętla zawiera węzły (to jest i ) i ustawiając t=0 jako wartość iteracji, gdy wtedy:

Jeśli jeden wskaźnik rzeczywiście wystarczy do wykrycia pętli za pomocą opisanego algorytmu, to musi istnieć przynajmniej rozwiązanie równania .

To równanie jest prawdziwe wtedy i tylko wtedy, gdy istnieje wartość dla t, która sprawia, że:

Kończy się to funkcją, , która generuje wartości t, które są poprawnymi rozwiązaniami równania opisanego powyżej:

W ten sposób udowodniono, że jeden wolny wskaźnik i jeden szybki wskaźnik wystarczą do wykrycia warunków pętli w połączonej liście.

Dystans pokonany przez slowPointer przed spotkaniem = x + y

Dystans pokonany przez fastpointera przed spotkaniem = (x + y + z) + y = x + 2y + z

Ponieważ fastPointer porusza się z podwójną prędkością slowpointera, a czas jest stały dla obu, gdy dotrze do miejsca spotkania.

Więc używając prostej relacji prędkości, czasu i odległości 2 (x+y)= x + 2Y + z = > x+2Y+z = 2x+2Y = > x=z

Stąd poprzez przesunięcie slowpointera na początek listy linked i zrobienie zarówno slowpointera jak i fastPointer do poruszania się po jednym węźle na raz, oba mają taką samą odległość do pokonania .

Osiągną punkt, w którym pętla zaczyna się na liście połączonej.

Nie sądzę, że to prawda, że kiedy się spotykają, to punkt wyjścia. Ale tak, jeśli drugi wskaźnik(F) był wcześniej w miejscu spotkania , niż ten wskaźnik będzie na końcu pętli zamiast na początku pętli, a wskaźnik (Y), który rozpoczął się od początku listy, skończy się na początku pętli. dla np:

Start f tak szybko i S tak wolno, że kończą spotkanie o 9 . Teraz, gdy zacznę S Od początku, to osiągnie w początek pętli tj. 7 ale f będzie na 16 ..

Proszę dać mi znać, jeśli się mylę

Druga część, stwierdzająca, że "aby znaleźć początek pętli, po prostu przesuń jeden wskaźnik z powrotem do początku listy, a następnie powtarzaj oba, aż się spotkają" jest błędna!

Jest poprawne tylko jeśli szybki wskaźnik okrążył pętlę dokładnie raz - tzn. że część przed rozpoczęciem pętli jest krótsza niż długość pętli - ale jeśli jest dłuższa, algorytm nie działa; możesz utknąć w nieskończonej pętli.

Spróbuj z połączoną listą z 11 pierwiastki, gdzie 11. wskazuje na 7.:

1 1 -> 3 2 -> 5 3 -> 7 4 -> 9 5 -> 11 6 -> 8 7 -> 10 8 -> 7 9 -> 9 9

-- loop detected

Przesuń jeden z powrotem, aby rozpocząć i zwiększyć je: 1 9 -> 2 10 -> 3 11 -> 4 7 -> 5 8 -> 6 9 -> 7 10 -> 8 11 -> 9 7 -> 10 8 -> 11 9 -> 7 10 -> 8 11 ->...

/* Algorithm : P2 is moving through the list twice as fast as P1.
   If the list is circular, it will eventually get around P1 and meet */

public boolean hasCycle()
{
  DoubleNode p1,p2;
  p1=p2=firstNode;    //Start with the first loop

  try
  {
    while (p2 != null)     //If p2 reaches end of linked list, no cycle exists
    {
        p1=p1.next;   //Move to next
        p2=p2.next.next; //Move to 2 steps next
        if(p1==p2)
           return true;     //p1 and p2 met, so this means that there is a cycle
    }
  }
  catch(NullPointerException npe)
  {
      //This means that p2 could not move forward
      return false;
  }

  return false;
}