# Java program to check whether linked list is palindrome or not

## Java program to check whether linked list is palindrome or not

Java program to check whether the linked list is palindrome or not. In this program, we have to check whether the given linked list is palindromic or not. A palindrome is a list which has the property of reversing itself. To check whether a number is palindrome or not, we traverse the list and check if any element from the starting half doesn’t  match with the ending half of a list then we say it’s not a palindrome number otherwise it is palindrome.

Java Program to check whether linked list is palindrome or not . Example :

After reversing it will stay as it is

1–>2–>3–>2–>1   (true) (It is a palindrome list)  ## Algorithm

We have used recursion here.

1. To check palindrome, we need the corresponding left and right elements. We can always get the left element in linked list and then move to next element easily but  starting from the end we can’t move forward in the linked list. This is the problem that we encounter. To avoid this we will use recursion.
2. There will be three parameters: start node, end node and the floor. Start node and end node represent the corresponding left and right node whose data must be same to be palindromic linked list. Floor basically represents the level of recursion.
3. We have kept the start node in heap section. Because when we fall one level in recursion then end node is automatically adjusted but we need to make change in start so that it points to the next node now. If it would be in stack frame, the changes we make to the start will go with the recursion level. And we would be at same start node again. For the changes to be there, we keep the start node in heap. Doing so, changes made in the start node always remain as it is even if we fall one level in recursion.
4. At every point we compare the data of start and end node. If they are not same then linked list is not palindrome. And we return false. Else check for the next corresponding nodes.
5. We check it until the floor >= half of the size of linked list. ## Java Program

```import java.util.*;

public class PrepInsta
{

public static void main (String[]args) throws Exception
{

ll.display ();

System.out.println (ll.isPalindrome ());

}

}

{
private class Node
{
int data;
Node next;

// Node constructor
// There are two fields in the node- data and address of next node
public Node (int data, Node next)
{
this.data = data;
this.next = next;
}
}

private Node tail;
private int size;

{
this.tail = null;
this.size = 0;

}

// Function to find the size of linked list
public int size ()
{
return this.size;
}

// Function to check whether linked list is empty or not
public boolean isEmpty ()
{
return this.size () == 0;
}

// Function to traverse and print the linked list
public void display ()
{
while (temp != null)
{
System.out.print (temp.data + "  ");

temp = temp.next;
}
System.out.println ("END");
}

{
// Create a temp node which points to head
Node temp = new Node (item, head);

// If linked list is empty, temp is the head and tail node both
if (this.size == 0)
{
}

// else set the head such that it now points to temp node
else
{

}

this.size++;
}

public boolean isPalindrome ()
{
HeapMover start = new HeapMover ();

}

//Function to check whether linked list is palindrome or not
private boolean isPalindrome (HeapMover start, Node end, int floor)
{

//Base case is when we reach end of linked list
if (end == null)
{
return true;
}

//Recursive calls
boolean rv = this.isPalindrome (start, end.next, floor + 1);

//If any recursive call results in false then return false
if (rv == false)
{
return false;
}

//Till floor is greater than 1/2 * size of linked list
if (floor >= this.size () / 2)
{

//If data of start node and end node is not same then it is not palindrome
if (start.node.data != end.data)
{
return false;

}

//Change start node so that it now points to the next node
else
{
start.node = start.node.next;
return true;
}

}
return rv;

}

//Class to keep a node in the heap
private class HeapMover
{
Node node;
}

}```
```Output: linked list is palindrome or not10-->20-->30-->40-->40-->30-->20-->10-->END                                                                                          true
```