0

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 ^ ^

*Edited
by mike_2000_17*: Fixed formatting

This Question has been **Answered**

0

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!

0

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..

0

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? :)

0

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
```

*Edited
by Taywin*: n/a

0

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

0

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.. !

*Edited
by mike_2000_17*: Fixed formatting

0

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.

0

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

*Edited
by mike_2000_17*: Fixed formatting

0

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

0

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?

0

```
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();
}
}
```

*Edited
by CLina*: n/a

0

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...

0

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

0

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..

0

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.

0

Yes, I'll start to practice now,, because tomorrow is the deadline ^ ^

>>>>>>>>

Thank you a lot..

*Edited
by CLina*: n/a

This question has already been answered. Start a new discussion instead.

Recommended Topics

Is there any simple way or online website that can convert The numerical string like"123-322-14365" to regular expression?