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