Java How to find a value in a linked list iteratively and recursively

Question

Hi

I have a method that has a reference to a linked list and a int value. So, this method would count and return how often the value happens in the linked list. So, I decided to make a class,

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

Then, the method would start with a

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; 
  }

So, I CHANGED this part, If I did this recursively, then I would have

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);

SO, is the recursive part correct now?

Answer 1

To get you started, you will find that if you run your findValue method with a non-null ListNode you will trigger an infinite loop. You will need to move your node to next on each recursion.

Answer 2

You need to somehow know where your list ends. Let's assume (as that's the easiest approach) that the last node has next set to null. You would then use this as check when to stop the iteration:

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;
}

The same approach can be used for recursive solution, except it's a bit messier because you'll need to pass your count as parameter to your recursive function call.

Answer 3

This looks like a bug in your sample code:

return findValue(x, valueToCount +1);

You should be incrementing the count, not the value being searched for. Also don't forget to move to the next node! So this should be:

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

Answer 4

Little Lisper path:

1 What is the result of null -- null

2 What is find result of a normal node -- (if node.value == aValue) return true if found

3 else try next node recursively

public boolean find (ListNode n, T value)

{

if (n==null)

return false;

if (n.element.equals(value))

 return true;

else

return find(n.next, value);

}**