# Solution by rohitnandi12

• 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;

}
private boolean isPalindromeUtil(ListNode right) {

/* stop recursion when pointer goes beyond List length */
if(right==null)return true;

/* Check If sub-list 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 {

while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}

slow = reverseList(slow);
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 read-only this approach is
not applicable.

** Thank You.. Happy Coding :)**

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.