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 ^ ^
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!
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..
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? :)
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
// doneI 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 :)
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.. !
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.
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
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()
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?
Please post the code as text and not as a picture...
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();
}
}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...
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;
How about the simple old fashioned
i.next = new Node(key);:)
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..
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.
Yes, I'll start to practice now,, because tomorrow is the deadline ^ ^
>>>>>>>>
Thank you a lot..