Algorytmy i struktury danych · Middle · Pytanie 25 z 75
Jak znaleźć środek listy wiązanej w jednym przejściu?
- ✓Poprawna odpowiedź: Wolny i szybki wskaźnik: gdy szybki dojdzie do końca, wolny jest w środku
- 2Odczytać właściwość długości listy i skoczyć do
length / 2 - 3Odwrócić listę i iść z obu końców, aż się spotkają
Wyjaśnienie
Lista jednokierunkowa nie zna swojej długości, więc inaczej potrzebne byłyby dwa przejścia. Sztuczka z wolnym i szybkim wskaźnikiem znajduje środek w jednym przejściu z O(1) pamięci.