Предположим, что есть односвязный список, длина которого неизвестна. Мы хотим найти узел с M шагами к хвосту.
Например, одиночный список выглядит так:
(А) -> (В) -> (С) -> (Х) -> (У)
и М = 2.
Тогда на выходе должен быть указатель на (C).
Когда я сталкиваюсь с этой викториной, моя первая реакция - пройти по односвязному списку, чтобы получить длину N. Затем пройти по одиночке второй раз, но только вперед N-M-1 шагов. Сложность по времени составляет O (n), а сложность по пространству - O (1).
Тогда мне нужно найти решение, чтобы сделать это одним способом. Решение состоит в том, чтобы иметь два указателя. Второй указатель на М шагов позади первого указателя. Эти два указателя движутся вперед с одинаковой скоростью. Когда первый указатель достигает хвоста, второй указатель является результатом.
После глубокого размышления над этим вопросом я действительно не верю, что второе "хитрое" решение превосходит первое. Это односторонний ход, но он также включает 2 * N-M назначения указателя.
Есть мысли по этому вопросу?
Есть ли другое решение, которое действительно быстрее?