Проблем 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-тия възел на свързан списък от края.

Това е!! Решихме въпроса!!