Answered # How to find max recursively in linked-list?

apines 116 Discussion Starter CLina apines 116 Taywin 311 apines 116 Discussion Starter CLina apines 116 Discussion Starter CLina apines 116 Discussion Starter CLina Discussion Starter CLina apines 116 Discussion Starter CLina Discussion Starter CLina apines 116 Discussion Starter CLina

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 3 Years Ago by mike_2000_17*: Fixed formatting

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 6 Years Ago 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 3 Years Ago 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 3 Years Ago 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 6 Years Ago 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 6 Years Ago by CLina*: n/a

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

Recommended Articles

Help! I want to create a java program that finds the highest even integer among the values entered by the user. Stop asking values when a value less than 1 have been entered. If no even integer is entered, display "No Even Integer"

Here is the sample output that I ...

Hello All ...

Iam Getting An Error With try to excecute the stored procedure .

I have Have Sql database , the stored procedure like so :

```
USE [MPRS]
GO
/****** Object: StoredProcedure [dbo].[Search_Licenses_By_Number] Script Date: 26-Nov-16 8:06:52 AM ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
ALTER PROCEDURE ...
```

I don’t want at this stage work on a big separate project as I've already got plenty ...