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 :

Given Linked list is 1–>2–>3–>2–>1

After reversing it will stay as it is

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

Java program to check whether the given linked list is palindrome or not

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 to check whether the given linked list is palindrome or not

Java Program

import java.util.*;

public class PrepInsta
{

  public static void main (String[]args) throws Exception
  {
    LinkedList ll = new LinkedList ();
      ll.addFirst (10);
      ll.addFirst (20);
      ll.addFirst (30);
      ll.addFirst (40);
      ll.addFirst (40);
      ll.addFirst (30);
      ll.addFirst (20);
      ll.addFirst (10);

      ll.display ();

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

  }

}

class LinkedList
{
  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 head;
  private Node tail;
  private int size;

// Linked list constructor
  public LinkedList ()
  {
    this.head = null;
    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 ()
  {
    Node temp = head;
    while (temp != null)
      {
	System.out.print (temp.data + "  ");

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

// Function to add a node in beginning of linked list
  public void addFirst (int item)
  {
// 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)
      {
	this.head = this.tail = temp;
      }

// else set the head such that it now points to temp node
    else
      {
	this.head = temp;

      }

    this.size++;
  }

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

    start.node = this.head;

    return this.isPalindrome (start, this.head, 0);

  }

//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 not
10-->20-->30-->40-->40-->30-->20-->10-->END
true