# Is Palindrome

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

## #

QuestionGiven 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 StringWe form a string by iterating through the linked list and then reversing the string to compare with the original.

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 StackIn 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.

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 PointersHere 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.

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 OptimisedHere 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.

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)`