Check if a Singly Linked List is Palindrome
Check if a Singly Linked List is Palindrome
In this section, we have given a singly linked list, and we need to check whether the given list is a palindrome.
Example:
1 -> 2 -> 3 -> 3 -> 2 -> 1
Output:
True
Method 1: Using a Stack
In this method, we will use the stack of linked list nodes and perform the following steps:
- First, it will traverse the entire linked list from the first to the last node and push every visited node to the stack.
- Next, it will traverse the linked list one more time. After this, it will pop a node from the stack and compare the data of popped node with the node which is visited currently.
- Finally, if data is matched of all nodes, it returns true, else false.
Java Program to implement the Method 1
import java.util.*;
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
public class Palindrome
{
/* Function to print linked list */
void printList(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}
/* Check whether the linked list is palindrome or not */
boolean isPalindrome(Node head)
{
Node temp = head;
boolean flag = true;
Stack<Integer> stack = new Stack<Integer>();
while (temp != null) {
stack.push(temp.data);
temp = temp.next;
}
while (head != null) {
int i = stack.pop();
if (head.data == i) {
flag = true;
}
else {
flag = false;
break;
}
head = head.next;
}
return flag;
}
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter the total no of elements in linked list: ");
int n = sc.nextInt();
System.out.println("Enter the elements of linked list: ");
int a1 = sc.nextInt();
Palindrome ob = new Palindrome();
Node head = new Node(a1);
Node tail = head;
for (int i = 1; i < n; i++)
{
int a = sc.nextInt();
tail.next = new Node(a);
tail = tail.next;
}
if(ob.isPalindrome(head) == true)
System.out.println("True");
else
System.out.println("False");
}
}
Output: -
Method 2: By reversing the linked list
This method uses the following steps to check the palindrome:
- It will first find the middle node of the linked list:
- Then, it will reverse the second half of the given linked list
- After this, it will compare the nodes of the first half and the second half to be the same or not.
- Then, we will make the original linked list as it is.
Java Program to implement the Method 2
import java.util.*;
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
public class Palindrome
{
Node head,slow, fast, second;
/* Function to print linked list */
void traverse(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}
/* Check whether the linked list is palindrome or not */
boolean isPalindrome(Node head)
{
slow = head;
fast = head;
Node prev_of_slow = head;
Node middle = null;
boolean res = true;
if (head != null && head.next != null) {
while (fast != null && fast.next != null) {
fast = fast.next.next;
prev_of_slow = slow;
slow = slow.next;
}
if (fast != null) {
middle = slow;
slow = slow.next;
}
second = slow;
prev_of_slow.next = null;
reverse();
res = compareLists(head, second);
/* Construct the original list back */
reverse();
if (middle != null) {
prev_of_slow.next = middle;
middle.next = second;
}
else
prev_of_slow.next = second;
}
return res;
}
/* Function for reverse the linked list */
void reverse()
{
Node prev = null;
Node current = second;
Node next;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
second = prev;
}
/* Function for compare both halves of the linked list*/
boolean compareLists(Node head1, Node head2)
{
Node temp1 = head1;
Node temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.data == temp2.data) {
temp1 = temp1.next;
temp2 = temp2.next;
}
else
return false;
}
if (temp1 == null && temp2 == null)
return true;
return false;
}
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter the total no of elements in linked list: ");
int n = sc.nextInt();
System.out.println("Enter the elements of linked list: ");
int a1 = sc.nextInt();
Palindrome ob = new Palindrome();
Node head = new Node(a1);
Node tail = head;
for (int i = 1; i < n; i++)
{
int a = sc.nextInt();
tail.next = new Node(a);
tail = tail.next;
}
if(ob.isPalindrome(head) == true)
System.out.println("True");
else
System.out.println("False");
}
}
Output:
