Solution Approach: First thing is we should know about palindrome. What is Palindrome? The list must be the same backwards and forwards such as 0-> 1 -> 2->1->0 This leads us to our first solution. This problem can solved in many ways,
Reverse and Compare
Iterative Approach
Recursive Approach
Among three i will first solve this problem using Iterative Approach just see the below
Implementation:
public boolean isPalindrome(LinkedListNode head)
{
LinkedListNode fast =head;
LinkedListNode slow =head;
Stack<Interger> stack=new Stack<Interger>();
while(fast!=null && fast.next !=null)
{
stack.push(slow.data);
slow=slow.next;
fast=fast.next.next;
}
if(fast!=null)
{
slow =slow.next;
}
while(slow!=null)
{
int top=stack.pop().intValue();
if(top!=slow.data)
{
return false;
}
slow=slow.next;
}
return true;
}
Now you can try others too......