Jak ustalić, czy połączona lista zawiera pętlę?

Question

Możliwe duplikaty:
find whether a loop in a linked list without two pointers
How to determine if a linked list has a cycle using only two memory locations.
Best algorithm to test if a linked list has a cycle

Podczas przygotowań do rozmowy kwalifikacyjnej, natknąłem się na następujące pytanie:

Jak można określić, czy Lista połączona (dowolnego typu) zawiera pętlę, używając additio końcowa złożoność przestrzeni O (1)? Nie można założyć, że pętla zaczyna się od pierwszego węzła (i oczywiście pętla nie musi zawierać wszystkich węzłów).

nie mogę znaleźć odpowiedzi, chociaż mam wrażenie, że to całkiem proste ...

Answer 1

łatwe. Utrzymuj dwa wskaźniki na liście. Na każdym kroku przesuń jeden wskaźnik o jedno łącze i przesuń drugi o dwa łącza. Sprawdź, czy wskazują na ten sam element. Jeśli tak, masz pętlę. Jeśli nie, powtarzaj, aż znajdziesz pętlę lub dojdziesz do końca listy.

Answer 2

Prawdopodobnie taka sama technika jak sprawdzenie, czy wykres jest drzewem (drzewa nie mają cykli), patrz this this question. Zaleca najpierw wyszukiwanie topologiczne lub głębokie pierwsze wyszukiwanie.

Answer 3

Miałem ten problem w prawdziwym kodzie na żywo w zeszłym tygodniu.

Wszystko co zrobiłem, to trzymałem wskaźnik (link) dla pierwszego elementu. Potem, kiedy przeglądałem listę, jeśli kiedykolwiek otrzymałem ten wskaźnik, wiem, że jest pętla.