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