Задача 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-го узла связного списка с конца.

Вот и все!! Мы решили вопрос!!