package com.dev.ds;
import java.util.Stack;
public class CheckLinkedListPalindrome {
Node head;
public static void main(String[] args) {
CheckLinkedListPalindrome p = new CheckLinkedListPalindrome();
p.insert("R");
p.insert("A");
p.insert("D");
p.insert("A");
p.insert("R");
//p.insert("P");
p.print();
boolean b = p.linkedListPlaindrome(p.head);
if(b){
System.out.println("Palindrome");
}else{
System.out.println("Not Palindrome");
}
}
private class Node{
String data;
Node next;
Node(String data){
this.data = data;
}
}
/**
*
* Time Complexity O(n)
* Space Complexity O(n)
*
* @param head
* @return
*/
public boolean linkedListPlaindrome(Node head){
if(head==null)
return false;
Stack<Node> stack = new Stack<>();
Node curr = head;
while(curr != null){
stack.push(curr);
curr = curr.next;
}
curr = head;
while(curr != null){
if(!curr.data.equals(stack.pop().data)){
return false;
}
curr = curr.next;
}
return true;
}
public void insert(String data){
Node newNode = new Node(data);
if(head == null){
head = newNode;
}else{
Node curr = head;
while(curr.next != null){
curr = curr.next;
}
curr.next = newNode;
}
}
public void print(){
if(head==null)
return;
Node curr = head;
while(curr != null){
System.out.print(curr.data + " ");
curr = curr.next;
}
}
}
Output: - R A D A R Palindrome