Algorytmy i struktury danych · Middle · Pytanie 24 z 75
Jak wykryć cykl na liście wiązanej z O(1) dodatkowej pamięci?
- ✓Poprawna odpowiedź: Wolny i szybki wskaźnik: spotkają się tylko wtedy, gdy jest cykl
- 2Policzyć węzły i porównać z właściwością długości listy
- 3Zapisywać każdy odwiedzony węzeł w
Seti szukać powtórek
Wyjaśnienie
To algorytm Floyda „żółw i zając”. Jeśli jest cykl, szybki wskaźnik w końcu dogoni wolnego; jeśli nie, dojdzie do null. Set też działa, ale zajmuje O(n) pamięci.