Данный алгоритм можно реализовать рекурсивным и нерекурсивным способом. Рекурсивные решения обычно более понятны, но менее оптимальны. Например, рекурсивная реализация этой задачи почти в два раза короче нерекурсивной, но занимает O(n) пространства, где n — количество элементов связного списка.
При решение данной задачи помните, что можно выбрать значение k так, что при передаче k = 1 мы получим последний элемент, 2 — предпоследний и т.д. Или выбрать k так, чтобы k = 0 соответствовало последнему элементу.
Решение 1. Размер связного списка известен
Если размер связного списка известен, k-й элемент с конца легко вычислить (длина — k). Нужно пройтись по списку и найти этот элемент.
Решение 2. Рекурсивное решение
Такой алгоритм рекурсивно проходит связный список. По достижении последнего элемента алгоритм начинает обратный отсчет, и счетчик сбрасывается в 0. Каждый шаг инкрементирует счетчик на 1. Когда счетчик достигнет k, искомый элемент будет найден.
Реализация этого алгоритма коротка и проста — достаточно передать назад целое значение через стек. К сожалению, оператор return не может вернуть значение узла. Так как же обойти эту трудность?
Подход А: не возвращайте элемент
Можно не возвращать элемент, достаточно вывести его сразу, как только он будет найден. А в операторе return вернуть значение счетчика.
public static int nthToLast(LinkedListNode head, int k) {
if (head == null) {
return 0;
}
int i = nthToLast(head.next, k) + 1;
if (i == k) {
System.out.println(head.data);
}
return i;
}
Решение верно, но можно пойти другим путем.
Подход Б: используйте C++
Второй способ — использование С++ и передача значения по ссылке. Такой подход позволяет не только вернуть значение узла, но и обновить счетчик путем передачи указателя на него.
node* nthToLast(node* head, int k, int& i) {
if (head == NULL) {
return NULL;
}
node* nd = nthToLast(head->next, k, i);
i = i + 1;
if (i == k) {
return head;
}
return nd;
}
Решение 3. Итерационное решение
Итерационное решение будет более сложным, но и более оптимальным. Можно использовать два указателя — p1 и p2. Сначала оба указателя указывают на начало списка. Затем перемещаем p2 на k узлов вперед. Теперь мы начинаем перемещать оба указателя одновременно. Когда p2 дойдет до конца списка, p1 будет указывать на нужный нам элемент.
LinkedListNode nthToLast(LinkedListNode head, int k) {
if (k <= 0) return 0;
LinkedListNode p1 = head;
LinkedListNode p2 = head;
for (int i = 0; i < k - 1; i++) {
if (p2 == null) return null;
p2 = p2.next;
}
if (p2 == null) return null;
while (p2.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
Разбор взят из перевода книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.
Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».