Даний алгоритм можна реалізувати рекурсивним і нерекурсівние способом. Рекурсивні рішення зазвичай більш зрозумілі, але менш оптимальні. Наприклад, рекурсивна реалізація цього завдання майже в два рази коротше нерекурсивною, але займає O (n) простору, де n - кількість елементів зв'язкового списку.
При вирішення цього завдання пам'ятайте, що можна вибрати значення k так, що при передачі k = 1 ми отримаємо останній елемент, 2 - передостанній і т.д. Або вибрати k так, щоб k = 0 відповідало останньому елементу.
Рішення 1. Розмір зв'язного списку відомий
Якщо розмір зв'язного списку відомий, k-й елемент з кінця легко обчислити (довжина - k). Потрібно пройтися по списку і знайти цей елемент.
Рішення 2. Рекурсивне рішення
Такий алгоритм рекурсивно проходить зв'язний список. Після досягнення останнього елемента алгоритм починає зворотний відлік, і лічильник скидається в 0. Кожен крок інкрементує лічильник на 1. Коли лічильник досягне k, шуканий елемент буде знайдений.
Реалізація цього алгоритму коротка і проста - досить передати назад ціле значення через стек. На жаль, оператор return не може повернути значення вузла. Так як же обійти ці труднощі?
Підхід А: чи не повертайте елемент
Можна не повертати елемент, досить вивести його відразу, як тільки він буде знайдений. А в операторі return повернути значення лічильника.
Рішення вірно, але можна піти іншим шляхом.
Підхід Б: використовуйте C ++
Другий спосіб - використання С ++ і передача значення за посиланням. Такий підхід дозволяє не тільки повернути значення вузла, але і оновити лічильник шляхом передачі покажчика на нього.
Рішення 3. Ітераційне рішення
Ітераційне рішення буде більш складним, але і більш оптимальним. Можна використовувати два покажчика - p1 і p2. Спочатку обидва вказівники вказують на початок списку. Потім переміщаємо p2 на k вузлів вперед. Тепер ми починаємо переміщати обидва покажчика одночасно. Коли p2 дійде до кінця списку, p1 буде вказувати на потрібний нам елемент.