How to find max recursively in linked-list?

[CLina]

Hello everybody!

I have to Questions to ask please:
1) How can I find the maximum value in a single linked-list recursively?

this is what I tried to do:

int findMax(int key){
    Node max=head;
    while (max != null){
        if (max < max.getKey())
    return(max.getNext());
    }

}

it ends up to an error.. :(

2) How can check palindrome in a single linked-list recursively?

Thank you for All ^ ^

[apines]

The solution you have provided for the first question is not recursive. You can have a recursion that will stop when max.next() is null, and otherwise will return the max value between the current node and the next node.

int findMax(Node node)
{
   if(node.next() == null)
   {
      return node.getKey();
   }
   else
   {
      return max(node.getKey(), findMax(node.next()));
   }
}

And you will need a method that will call the recursion with head

int findMax()
{
   if(head == null)
   {
      return null;
   }
   else
   {
      return findMax(head);
   }
}

Regarding the second question - how would you check for a palindrome in a non-recursive manner? Try to do this and maybe the recursion will seem more clear.

Good luck!

[CLina]

Thank you for quick helping, I'll try to run the code at home.
But I still don't understand how does the code work, where is the comparison exactly done! Thank you for explaining..

[apines]

The comparison is done in this line:

return max(node.getKey(), findMax(node.next()));

Where you return the max of the current result and the result of the next recursion call. Try to visualize it... can you see it? :)

[Taywin]

I understand that it is difficult to understand recursive when you learn about it the first time. (I did have difficulty understanding it as well when I first learned about it.) One way to be more clear about it is to follow its iteration and write it down in a paper. Write all variables you use in the function call before a call. Then, write them all again after the first call, and keep doing it until you hit the base case. Try to make the limit the call to at most 3 call before it hits the base case, so you would get an idea how it works.

// i.e.
// aList: 5 -> 10 -> 4 -> null
//
// findMax() 1st iteration
// current node is 5, next node is 10
// 10 (next node) is not null, comparing 5 with whatever comes back **
// findMax() 2nd iteration
// current node is 10, next node is 4
// 4 is not null, comparing 10 with whatever comes back **
// findMax() 3rd iteration
// current node is 4, next node is null
// next node is null, return 4

// now it is time to come back to each of the recursive call
// compare 4 with 10, 10 is max so return 10
// compare 5 with 10, 10 is max so return 10
// done

[apines]

I agree with Taywin, recursions can be hard at the beginning. Let us try and review our code for a linked list of length 4, containing [22]->[43]->[107]->[45]->[null].
First, we call findMax(), it will call findMax(Node node) where node == head:

//Iteration 1

int findMax(Node node) // node == head, and head.getKey() == 22
{
   if(head.next() == null) //we know that head.next() != null, so we are going to the else clause.
   {
      return node.getKey();
   }
   else
   {
      return max(node.getKey(), findMax(node.next())); //meaning we need to return the max between 22 and the result of findMax(head.next()).
   }
}

The method then needs to call to findMax(head.next()) in order to determine which one is bigger:

//Iteration 2

int findMax(Node node) // node == head.next(), and head.next()getKey() == 43
   if(head.next() == null) //we know that node.next() != null, so we are going to the else clause.
   {
      return node.getKey();
   }
   else
   {
      return max(node.getKey(), findMax(node.next())); //meaning we need to return the max between 43 and the result of findMax(head.next()).
   }
}

And again, the method needs to call to findMax(head.next().next()) in order to determine which one is bigger:

//Iteration 3

int findMax(Node node) // node == head.next().next(), and head.next().next().getKey() == 11
   if(head.next() == null) //we know that node.next() != null, so we are going to the else clause.
   {
      return node.getKey();
   }
   else
   {
      return max(node.getKey(), findMax(node.next())); //meaning we need to return the max between 107 and the result of findMax(head.next()).
   }
}

And yet again, the method has to call the findMax(head.next().next().next()) in order to determine which one is bigger, 107, the value of the current node checked, or the next node:

//Iteration 4

int findMax(Node node) // node == head.next().next().next(), and head.next().next().next().getKey() == 45
   if(head.next() == null) //this node is the last one, and its next points to null (head.next().next().next().next() == null), therefore we are inside the if clause.
   {
      return node.getKey(); //simply return 45.
   }
   else
   {
      return max(node.getKey(), findMax(node.next())); //meaning we need to return the max between 45 and the result of findMax(head.next()).
   }
}

Now, all the results are coming back to the calling methods. Iteration 4 returned the value of 45 to the calling method, which is the method shown in iteration 3. Meaning that iteration 3 now needs to compute:

return max(107, 45)

That means that iteration 3 returns 107 to the calling method, iteration 2. The method in iteration 2 will also need to compute and return its value:

return max(43, 107)

Meaning iteration 2 will return 107 to its calling method, iteration 1. Iteration 1 will also calculate and return:

return max(22, 107)

Meaning that the final result that will return to the user is 107, which is indeed the highest number stored in the linked list.

I hope that this step-by-step dive into the recursion helped you to understand the concept. Don't worry, even though it's hard to grasp at the beginning, it becomes easier as you practice it :)

[CLina]

Thaaaaaank you for your great help, I really appreciate your time and effort.
Now I see the code more clearer as tracing.. but still not creating a new algorithm ^^

I run the code in my program, but the keyword ( max ) in the last line was not
initialized!

I try to omit the ( max ) and edit the code like this:

int findMax(Node node){

            if(node.getNext() == null)
      {
      return node.getKey();
      }
      else
      {
        int m = findMax(node.getNext());
            if (node.getKey()> m)
            return (node.getKey());
            return m;

}
}

but it always return the first element.. !

[apines]

You can't omit the max, since this is the actual line that does the comparison between the two numbers - the number in the current node, and the number returned from the following nodes in the recursion. You can implement a max method of your own, or simply use the max(int a, int b) provided in the Math class.

[CLina]

I did the following max method:

int max (int a, int b){
    Node node;
    int maximam;
    if (node.getKey() > node.getNext())
        maximam = node.getKey();
        return maximam;
}

but there is an error :

operator > cannot be applied to int,Node

Sorry for annoying you all

[apines]

Ok...
First, the method is accepting two integers, a and b - and then you trying to compare the nodes instead of a and b in question. The method should accept a and b and return the higher value of the two.

public int max(int a, int b)
{
   if(a > b)
   {
     return a;
   }
   return b;
}

Can you see the difference between this and what you wrote?
Second, regarding the complication error - you are trying to compare an int (node.getKey()) and a node (node.getNext()).
Perhaps you want to compare it with node.getNext().getKey()

[CLina]

aha, so the comparison doesn't take parameters of the class type ( Node ), only int.
.....
Now the program compiles with no error, but it still returns only the first value ( key ),
I captured the code that I did to create a linked list, to find out the problem:

the main program

the class Node

Is the way that I create the list right?

[apines]

Please post the code as text and not as a picture...

[CLina]

import java.util.*;
import java.util.Scanner;

 class Node{

    int key;
    Node next; 
    Node head;    
    
    public Node (){
    
        this.key=key;
        next = null;
    }    
        
    public    Node (int a){
    
        key = a;
        next = null;
        head = null;
    
    }
    
    public void setNext(Node n){
        next = n;
    }
    
    public Node getNext(){
        return next;
    }
    
    public int getKey(){
        return key;
    }
    
    public void newNode(int n){
        key = n;
        Node i ;
        if (head == null)
                head = new Node(key);
            else
            {
                i = head;
            
                while (i.getNext() != null)
                    i = i.getNext();
            }
    }
    
    
      public int max(int a, int b){
           if(a > b)
           {
         return a;
          }
           return b;
    }
      
      int findMax(Node node){
          
   
              if(node.getNext() == null)
      {
      return node.getKey();
      }
      else
      {
          int m = findMax(node.getNext());
     
      return max(node.getKey(), findMax(node.getNext()));
      }
   }
   
   
      void findMax(){
     
          System.out.println(" The maximum value is: " + findMax(head));
      
    }
    
} 

public class maxRecursion {
    
    public static void main(String[] args) {
        
   
        Node myList = new Node();
        Scanner input=new Scanner(System.in);
        System.out.println("Enter a set of integers, press y to continue and x to stop: ");
        int n;
        char exit = ' ';
    
        do{    
            System.out.print("Enter an integer:  ");
            n = input.nextInt();
            myList.newNode(n);
            System.out.print("continue?  ");
            exit = input.next().charAt(0);
 
          }while (exit != 'x' );
          myList.findMax();
        
        
    }
}

[apines]

Your newNode(int n) method only inserts the new node if (head == null), but does nothing afterwards except to iterate all the way to the end.

public void newNode(int n)
{
   key = n;
   Node i ;
   if (head == null)
   {
      head = new Node(key); // Great, we will have a new node here.
   }
   else
   {
      i = head;
      while (i.getNext() != null)
      {
         i = i.getNext();
      }
      // ok, i is the last node here... now you need to insert the node.
   }
}

Your list only has the first node inserted, which can explain your results...

[CLina]

public void newNode(int n)
{
   key = n;
   Node i ;
   if (head == null)
   {
      head = new Node(key); // Great, we will have a new node here.
   }
   else
   {
      i = head;
      while (i.getNext() != null)
      {
         i = i.getNext();
      }
      
        i.getNext()= new Node(key);
      // ok, i is the last node here... now you need to insert the node.
   }
}

Th insertion state is unexpected type,
I tried with:
i.getNext()= new Node(key);
i.getNext()= key;

[apines]

How about the simple old fashioned

i.next = new Node(key);

:)

[CLina]

Yeeeeeh!,,
it's reeaally working... :)

This is my first try to create a linked list.. I need to get more trainings on that..
Thank you so much for all ^ ^

.......
for the second question ( palindrome ) I prefer to create another thread to be a whole complete reference for other..

[apines]

Glad to hear that it's working! Try to work on the palindrome with the techniques you have learned :)

Please mark the thread as solved.

[CLina]

Yes, I'll start to practice now,, because tomorrow is the deadline ^ ^
>>>>>>>>
Thank you a lot..