Primary Thoughts
What is a Palindrome?
A word, phrase, or sequence that reads the same backwards as forwards, e.g. "madam" or "nurses run"
With respect to linked list example of palindrome will be "1>2>1" and not a palindrome will be "1>2>3".
Test Cases
Try to create your own test cases. You can take help of the interviewer, to validate your understanding of the problem.
T1 : [1,2,3,4,3,2,1] // true
T2 : [1,2,3,3,2,1] // true
T3 : [1,1] // true
T4 : [] // true
T4 : [1,2,3,4,2,1] // false
Various Approaches
Approach #1
Using a stack. In first traversal, push all the elements in stack. Traverse the list again, this time pop one element and compare it with the current list element, repeat until both the elements are equal. Time Complexity O(n), Space Complexity O(n).
Approach #2
Using Recursion. Idea is the same as above, but in this approach functional call stack is used as a container. Recursively traverse to the end of the list, when end is reached, traverse back and compare the last node with first node and so on.
Java
class Solution {
private ListNode left = null;
public boolean isPalindrome(ListNode head) {
this.left = head;
return isPalindromeUtil(head);
}
private boolean isPalindromeUtil(ListNode right) {
/* stop recursion when pointer goes beyond List length */
if(right==null)return true;
/* Check If sublist is palindrome or not.*/
boolean isRestPallin = isPalindromeUtil(right.next);
if(!isRestPallin)return false;
boolean isCurrentMatch = (left.val == right.val);
left = left.next;
return isCurrentMatch;
}
}
**Complexity Analysis**
* Time complexity : $$O(n)$$
* Space complexity : $$O(1)$$. If functional call stack is neglected.
Approach #3 Reversing the linked list [Accepted]
Algorithm
 Use two pointer to reach the half of the list.
 Reverse the second half of the list
 compare the first and the new reversed half of the list
 if both are exactly equal it is a palindrome
Java
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
slow = reverseList(slow);
fast = head;
while(slow!=null && slow.val==fast.val){
slow = slow.next;
fast = fast.next;
}
return slow==null;
}
private ListNode reverseList(ListNode node){
if(node == null)return null;
if(node.next == null)return node;
ListNode temp = reverseList(node.next);
node.next.next = node;
node.next = null;
return temp;
}
}
Complexity Analysis

Time complexity : $$O(n)$$

Space complexity : $$O(1)$$
Only downfall to this approach is the actual list is modified.If the input is readonly this approach is
not applicable.
** Thank You.. Happy Coding :)**