Задача 11.
Реализуйте алгоритм поиска k-го до последнего элемента односвязного списка.
Input: 1->2->3->4->5->6 k = 2 Output: 5
Подход 1:
1. Получить длину связанного списка
2. Добраться до n-го узла, вычитая Listlength - k
3. Перемещайтесь по списку до тех пор, пока значение n не станет равным 0, что будет k-м узлом связанного списка с конца.
Временная сложность: O(N)
Пробел: O(1)
Подход 2:
Здесь мы просматриваем список дважды, один раз, чтобы получить длину связанного списка. Второй — добраться до k-го узла связанного списка. Можем ли мы придумать другой альтернативный подход для определения длины связанного списка?
Мы можем использовать метод двух указателей, чтобы найти длину связанного списка.
Временная сложность: O(N)
Космическая сложность: O(1)
Здесь временная сложность кода по-прежнему O(N), однако, чтобы получить длину списка, мы не повторяем список дважды. Длина списка получается с использованием техники быстрого и медленного указателя.
Подход 3:
Можем ли мы получить список k-й вершины, не зная заранее длину?
Мы можем использовать метод быстрого и медленного указателя, который мы использовали в нашем предыдущем алгоритме. Мы можем увеличить быстрый указатель k раз до этого. После этого мы можем начать увеличивать как быстрый, так и медленный указатель, поскольку быстрый указатель достигает конца списка. Медленный указатель достигнет K-го узла связанного списка.
Временная сложность: O(N)
Космическая сложность: O(1)
Приведенные выше решения получают значение k-го узла связанного списка, проходя по связанному списку ровно один раз.
Итак, это были различные решения задачи получения n-го узла связного списка с конца.
Вот и все!! Мы решили вопрос!!