Реализовать алгоритм для нахождения kth в последнем элементе односвязного списка

Question

Реализовать алгоритм для нахождения k-го последнего элемента отдельно связанного списка.

Является хорошим решением вышеупомянутой проблемы, реверсив связанный список, затем пересекаясь снова и получая k-й элемент?

Answer 1

Прежде всего, это список singly-linked. Так что это хороший намек на то, что вы не должны пытаться изменить его, потому что для копирования вам понадобится столько же хранилища.

Вы можете использовать модифицированную версию алгоритма черепаха-заяц:

• Используйте hare указатель на начало списка
• переместить его по меньшей мере K элементы прочь
• Если вы нажмете last Элемент раньше, тогда вы не можете найти Kth для последнего элемента.
• Поместите turtle указатель на начало списка
• Теперь запускает hare указатель на конец списка, каждый раз, когда вы перемещаете указатель hare, перемещает turtle.

Когда hare указатель достигнет конца списка, turtle находится на Kth до последнего элемента.