# Is Palindrome

Leetcode link: https://leetcode.com/problems/palindrome-linked-list

## Question#

Given the head node of a singly linked list, determine if it is a palindrome or not.

A palindrome reads the same from front to back and back to front. Example: `racecar` or `madam` or `radar` or `redder`.

## Method 1 - Using String#

We form a string by iterating through the linked list and then reversing the string to compare with the original.

def is_palindrome(head):
s = ""
curr = head
while curr:
s += curr.data
curr = curr.next
return s == s[::-1]

Overall, analysing the time complexity, we get `O(n)`for iterating through linked list, `O(n)` for reversing string. Overall

• Time complexity: `O(n)`

## Method 2 - Using Stack#

In this method, we use a list as a stack and append to it all the elements while iterating the linked list. Then we compare element by element while iterating the linked list in a second loop.

def is_palindrome(head):
curr = head
stack = []
while curr:
stack.append(curr.data)
curr = curr.next
curr = head
while curr:
if(curr.data != stack.pop()):
return False
curr = curr.next
return True

Analysing this solution, we get `O(n)` time complexity to iterate the linked list twice.

We also need `O(n)` space for the stack to store `n` elements of the linked list.

• Time complexity: `O(n)`
• Space complexity: `O(n)`

## Method 3 - Two Pointers#

Here we use two pointers, `p1` and `p2` at the start and end of the linked list respectively. We increment `p1` and decrement `p2` in their positions to check the value.

def is_palindrome(head:
if head is None:
return True
p1 = head
p2 = head
# list to store previous nodes
prev = []
while p2:
prev.append(p2)
p2 = p2.next
# p2 is at the last node
p2 = prev[-1]
# loop with both pointers
count = 1
while(count <= len(prev) // 2 + 1):
if(prev[-count].data != p1.data):
return False
p1 = p1.next
count += 1
return True

Analysing this, we get a time complexity of `O(n)` as we iterate the linked list fully once with `p2` and then again for half of the linked list which is `O(n/2)`.

We also need a space of `O(n)` as we are storing all the nodes in an array.

• Time complexity: `O(n)`
• Space complexity: `O(n)`

## Method 4 - Two Pointers Optimised#

Here we use still use two pointers, but we attempt to reverse the second half of the linked list and compare it.

For example, if we have a string `redder`, reversing the second half gives us `redred`. Now if we have a pointer at the start and the middle, we can increment them step by step and compare the values.

class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if(head is None):
return True
p1 = head
p2 = head
# bring p1 to middle and p2 to end
while p2 and p2.next:
p1 = p1.next
p2 = p2.next.next
# reverse the second half of the linked list
p1 = self.reverse(p1)
# iterate from start to end
p2 = head
while (p1 and p2):
if(p1.val != p2.val):
return False
p1 = p1.next
p2 = p2.next
return True
# Auxillary method to reverse linked list
def reverse(self, head):
if(head is None):
return
prev = None
curr = head
next = head.next
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev

Analysing this, we are iterating the linked list with `O(n)` time complexity. We are using no auxillary space, hence `O(1)` space.

• Time complexity: `O(n)`
• Space complexity: `O(1)`