Вы используете односвязный список, что означает, что вы можете перемещаться по нему только в одном направлении, а именно вперед, то есть от первого узла к последнему узлу.
Алгоритм состоит в том, чтобы обходить список от первого до последнего узла и сравните каждый узел item с элементом, который вы ищете. Также вам понадобятся две переменные, которые будут содержать индекс в списке как последнего (т.е. предельного), так и второго последнего (т.е. предпоследнего) вхождения искомого элемента. Обе эти переменные должны иметь начальные значения -1 (минус один).
Когда вы нажмете первое вхождение искомого элемента, обновите переменную окончательного индекса. Когда вы достигнете следующего вхождения, установите предпоследний индекс на конечный индекс, а затем обновите конечный индекс.
Повторите для каждого последующего вхождения искомого элемента, то есть установите предпоследний индекс на конечный индекс, а затем установите окончательный индекс на индекс текущего узла в списке. Следовательно, если искомый элемент встречается в списке только один раз или не встречается вообще, предпоследний индекс будет равен -1.
При написании рекурсивного метода первое, что вам нужно, это условие, которое будет прекратить рекурсию. Если условие истинно, вернуть соответствующее значение. Если условие ложно, измените аргументы метода и вызовите тот же метод с измененными аргументами. Завершающим условием в вашем случае является нулевой узел.
Поскольку список не является массивом, вам также необходимо отслеживать индекс текущего узла, чтобы иметь возможность вернуть его из вашего рекурсивного метода.
Вот моя реализация. Я создал LinkList класс, который содержит список вашего Node класса. Класс LinkList позволяет мне изначально создать связанный список. Я также добавил метод toString() к классам Node и LinkList, чтобы помочь визуализировать, как выглядит список. Метод main() служит тестом рекурсивного метода. При первом вызове рекурсивного метода используется первый узел в списке, индекс которого равен 0 (ноль).
public class Penultim {
public static void main(String[] args) {
LinkList list = new LinkList();
list.append('a');
list.append('b');
list.append('a');
list.append('b');
list.append('c');
list.append('d');
list.append('e');
list.append('f');
list.append('b');
System.out.println(list);
System.out.println(list.getPenultimateOccurrenceIndex('b', list.getHead(), 0, -1, -1));
}
}
class Node {
private char item;
private Node next;
public Node(char item, Node next) {
this.item = item;
this.next = next;
}
public char getItem() {
return item;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public String toString() {
return item + "->";
}
}
class LinkList {
private Node head;
public void append(char item) {
if (head == null) {
head = new Node(item, null);
}
else if (head.getNext() == null) {
head.setNext(new Node(item, null));
}
else {
Node node = head.getNext();
while (node != null) {
if (node.getNext() == null) {
node.setNext(new Node(item, null));
break;
}
node = node.getNext();
}
}
}
public Node getHead() {
return head;
}
public int getPenultimateOccurrenceIndex(char item,
Node node,
int ndx,
int penultimate,
int ultimate) {
if (node == null) {
return penultimate;
}
else {
if (node.getItem() == item) {
if (ultimate >= 0) {
penultimate = ultimate;
}
ultimate = ndx;
}
return getPenultimateOccurrenceIndex(item,
node.getNext(),
ndx + 1,
penultimate,
ultimate);
}
}
public String toString() {
StringBuilder sb = new StringBuilder();
Node node = head;
while (node != null) {
sb.append(node);
node = node.getNext();
}
return sb.toString();
}
}
Выход при выполнении вышеуказанного кода:
a->b->a->b->c->d->e->f->b->
3