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

У меня есть метод со ссылкой на связанный список и значение 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);

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


java recursion iteration algorithm linked-list
person Roxy    schedule 10.10.2009    source источник
comment
... и ваш вопрос: "Это сработает?"   -  person akf    schedule 10.10.2009
comment
да, мне было интересно, может ли это работать   -  person Roxy    schedule 10.10.2009

Ответы (4)


arrow_upward
1
arrow_downward

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

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 as для вызова рекурсивной функции.

person ChssPly76    schedule 10.10.2009
comment
вы можете просто добавить еще один int к своей подписи, сделать while if и изменить currentNode=currentNode.next; на return findValue(x,valueToCount,count); - person akf; 10.10.2009
comment
@Jacky, в приведенном выше примере есть счетчик в выражении if/else, комментарий выше дает вам подсказки для принятия рекурсивного метода. - person akf; 10.10.2009
comment
Хорошо, спасибо за подсказки, это действительно помогло мне понять больше об этом :) - person Roxy; 10.10.2009

arrow_upward
1
arrow_downward

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

return findValue(x, valueToCount +1);

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

return 1 + findValue(x.next, valueToCount);
person finnw    schedule 10.10.2009
comment
В Java нет исключения хвостовых вызовов, поэтому нет смысла передавать счетчик в качестве дополнительного параметра-аккумулятора. - person Pete Kirkham; 10.10.2009
comment
Хорошо, теперь я понимаю, но как насчет оператора if. Я думаю, что это неправильно? должно ли быть if(x.next == null && x.value != valueToCount) { return 0; } это было бы правильно? - person Roxy; 11.10.2009
comment
@Pete, valueToCount - это искомое значение, а не аккумулятор. - person finnw; 12.10.2009
comment
@Jacky, if(x.next == null...) пропустит первый узел и не будет работать с пустым списком. - person finnw; 12.10.2009

arrow_upward
1
arrow_downward

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

  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);
}
person miz    schedule 20.05.2010

arrow_upward
0
arrow_downward

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

person akf    schedule 10.10.2009