A palindrome is a word or a collection of contiguous items which read the same from forward and backward, words like Mom, Wow are common examples of this kind. Checking if a string or array is a palindrome is a trivial task if you have some experience with for-loops and data structures. We could either employ the famous two-pointer technique or push all of the array elements in a stack and then compare each of the elements of the array going forwards with each of the items popped from the stack.
However, the same approach won't work in a straightforward way if you have a singly linked list. This is due to the fact that you can only move forwards and cannot access the end element in O(1) like that in an array and iterate backward from there as we do in the two-pointer technique.
Stack approach
It's quite straight-forward but extremely costly as we will analyze in a while.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
listStack = []
curr = head
while curr != None:
listStack.append(curr.val)
curr = curr.next
curr2 = head
while curr2 != None:
val = listStack.pop()
if val != curr2.val:
return False
curr2 = curr2.next
return True
We are passing reference to the head of the linked list and then initializing an empty array to be used as a stack. Then we iterate forwards and insert each item of the list into the stack. Since doing so would have the same elements from the list inside the array but this time in reverse order we can now compare each item from the list with that of the stack popped. As soon as there is a mismatch we terminate, the loop and return False otherwise if the entire loop passes, then it was a palindrome and return True.
Complexity analysis
Space complexity - O(n) since we are using extra space as a stack
Time complexity -
O(n) for passing through the list once + O(1) for appending each item + O(n) for passing through the list once again and comparing with popped stack item which should be constant time. Ignoring the constants the complexity approximately becomes 2 * O(n) ~ O(n)