Java Как найти значение в связанном списке итеративно и рекурсивно

Question

У меня есть метод, который имеет ссылку на связанный список и значение int.Таким образом, этот метод будет подсчитывать и возвращать, как часто значение встречается в связанном списке.Итак, я решил создать класс,

public class ListNode{ 
 public ListNode (int v, ListNode n) {value = v; next = n;)
 public int value;
 public ListNode next;
}

Затем метод будет начинаться с

public static int findValue(ListNode x, int valueToCount){
 // so would I do it like this?? I don't know how to find the value, 
 // like do I check it?
  for (int i =0; i< x.length ;i++){
    valueToCount += valueToCount; 
  }

Итак, я ИЗМЕНИЛ эту часть, Если я сделал это рекурсивно, то ябудет иметь

public static int findValue(ListNode x, int valueToCount) {
  if (x.next != null && x.value == valueToCount {
     return 1 + findValue(x, valueToCount);}  
  else 
   return new findvalue(x, valueToCount);

ТАК, рекурсивная часть теперь верна?

Answer 1

Путь Маленького Лиспера:

1. Что является результатом NULL - NULL

2. Что является результатом поиска нормального узла -

   if (node.value == aValue)
       return true;
   

   если найден

3. иначе попробуйте следующий узел рекурсивно

   public boolean find(ListNode<T> n, T value)
   {
     if (n==null)
      return false;
     if (n.element.equals(value))
        return true;
     else 
       return find(n.next, value);
   }
   

Answer 2

Вам нужно как-то знать, где заканчивается ваш список. Давайте предположим (поскольку это самый простой подход), что последний узел имеет next, установленный в ноль. Затем вы можете использовать это как проверку, когда останавливать итерацию:

public static int findValue(ListNode x, int valueToCount) {
    ListNode currentNode = x;
    int count = 0;
    while (currentNode.next!=null) {
      if (currentNode.value == valueToCount) {
        count++;
      }
      currentNode = currentNode.next;
    }
    return count;
}

Тот же самый подход может быть использован для рекурсивного решения, за исключением того, что он немного сложнее, потому что вам нужно передать count в качестве параметра для вызова рекурсивной функции.

Answer 3

Это похоже на ошибку в вашем примере кода:

return findValue(x, valueToCount +1);

Вы должны увеличивать количество, а не искомое значение. Также не забудьте перейти к следующему узлу! Так что это должно быть:

return 1 + findValue(x.next, valueToCount);

Answer 4

Для начала вы обнаружите, что если вы запустите свой метод findValue с ненулевым ListNode, вы запустите бесконечный цикл. Вам нужно будет перемещать свой узел на next в каждой рекурсии.