Данный алгоритм можно реализовать рекурсивным и нерекурсивным способом. Рекурсивные решения обычно более понятны, но менее оптимальны. Например, рекурсивная реализация этой задачи почти в два раза короче нерекурсивной, но занимает O(n) пространства, где n — количество элементов связного списка.
При решение данной задачи помните, что можно выбрать значение k так, что при передаче k = 1 мы получим последний элемент, 2 — предпоследний и т.д. Или выбрать k так, чтобы k = 0 соответствовало последнему элементу.
Решение 1. Размер связного списка известен
Если размер связного списка известен, k-й элемент с конца легко вычислить (длина — k). Нужно пройтись по списку и найти этот элемент.
Решение 2. Рекурсивное решение
Такой алгоритм рекурсивно проходит связный список. По достижении последнего элемента алгоритм начинает обратный отсчет, и счетчик сбрасывается в 0. Каждый шаг инкрементирует счетчик на 1. Когда счетчик достигнет k, искомый элемент будет найден.
Реализация этого алгоритма коротка и проста — достаточно передать назад целое значение через стек. К сожалению, оператор return не может вернуть значение узла. Так как же обойти эту трудность?
Подход А: не возвращайте элемент
Можно не возвращать элемент, достаточно вывести его сразу, как только он будет найден. А в операторе return вернуть значение счетчика.
1 2 3 4 5 6 7 8 9 10 | 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++
Второй способ — использование С++ и передача значения по ссылке. Такой подход позволяет не только вернуть значение узла, но и обновить счетчик путем передачи указателя на него.
1 2 3 4 5 6 7 8 9 10 11 | 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 будет указывать на нужный нам элемент.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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-компанию».