Program to find if a LinkedList is a palindrome or not in Java ?

Hi there! today we are going to learn if a LinkedList is a palindrome or not in Java. We all know that a string or number is palindrome if when reads backwards it produces the same string or number. For eg. 343, NITIN, ABBA, etc.

How to find if a LinkedList is a palindrome or not in Java

Steps to find whether a LinkedList is a palindrome or not:-

1)First, we will store the data into a LinkedList
2)We will find the middle of the LinkedList →→←←
3)We break the LinkedList from there and create a separate LinkedList →→ ←←
4)We will reverse the second LinkedList →→
5)We will compare the data of both the LinkedList, node by node if found equal then its a palindrome otherwise not. →→ (= or ≠ ) →→
6)We will again reverse the second LinkedList and connect it with original LinkedList →→ ←←

Checking a LinkedList to be a palindrome or not in Java

import java.util.Scanner;

class Node {
  int data;
  Node next;

  Node(int d) {   //constructor
    data = d;
    next = null;
  }
}

public class palind {
  Node head;

  void printlist(Node head) // print the linkedlist
  {
    Node temp = head;
    while (temp != null) {
      System.out.print(temp.data + " ");
      temp = temp.next;
    }
    System.out.println();
  }

  public void addToTheLast(Node node)// add the node to the linkedlist in last
  {
    if (head == null)
      head = node;
    else {
      Node temp = head;
      while (temp.next != null) {
        temp = temp.next;
      }
      temp.next = node;
    }
  }

  public static void main(String[] args) // 3rd
  {
    @SuppressWarnings("resource")
    Scanner sc = new Scanner(System.in);
 System.out.println("enter test case");
    int t = 0;// test case
    if (sc.hasNext())
      t = sc.nextInt();

    while (t-- > 0) {
      System.out.println("enter size of linkedlist");
      int n = sc.nextInt();
      palind llist1 = new palind();
      System.out.println("enter elements of linkedlist");
      int a1 = sc.nextInt();
      Node head = new Node(a1);
      llist1.addToTheLast(head);// add node to link list
      for (int i = 1; i < n; i++) {
        int a = sc.nextInt();
        llist1.addToTheLast(new Node(a));
      }

      codespeedy d = new codespeedy();
         d.palindr(llist1.head);
        
    }
  }
}

class codespeedy {
  void  palindr(Node head) // 4th

  {
    Boolean count = false;
    Node fast = head, slow = head;
    if (slow.next == null)         // for one node
      count= false;
    if (fast.next.next == null)        // for 2 node
      count= false;
    while (fast.next != null && fast.next.next != null)   // to get the middle node
    {
      fast = fast.next.next;
      slow = slow.next;
    }

    Node h2 = slow.next;
    slow.next = null;            // middle of linklist
    Node h3 = reverse(h2);      // get the reverse of linklist
    
  
    Node t1 = head, t2 = h3;
    while (t2 != null)            // check palindrome
    {
      if (t1.data != t2.data) {
        count = false;
        break;
        // return count ;
      }
      count = true;
      t1 = t1.next;
      t2 = t2.next;

    }
  
    Node h4 = reverse(h3);
    slow.next = h4; // reconnect final list
    if (count == true)
      System.out.println("list is a palindrome");
    else
      System.out.println("liist is not a palindrome");
 
  
    
  }

  Node reverse(Node head)// reverse function 5th
  {

    Node c = head, p = null, n = null;
    if (c.next == null) {
      return head;
    }
    while (c != null) {
      n = c.next;
      c.next = p;
      p = c;
      c = n;
    }
    head = p;
    return head;
  }
}

The output is given below:

enter test case
1
enter size of linkedlist
5
enter elements of linkedlist
6
3
2
3
6
list is a palindrome

Hope you understand the code.

You may also read:

String Palindrome in Java

Java Program To Check A Number is Palindrome or Not

Check If A String Is Palindrome Or Not Ignoring The Case Of Characters In Java

Leave a Reply

Your email address will not be published. Required fields are marked *