From today, we will start doing the April LeetCoding Challenge. You can check the March LeetCoding Challenge problems on my profile.

## Problem Statement

Given the head of a singly linked list, return true if it is a palindrome.

**Example 1:**

```
**Input:** head = [1,2,2,1]
**Output:** true
```

**Example 2:**

```
**Input:** head = [1,2]
**Output:** false
```

**Constraints:**

The number of nodes in the list is in the range [1, 105].

0 <= Node.val <= 9

**Follow up:** Could you do it in O(n) time and O(1) space?

##
**Solution**

In this problem, we have to find whether a given LinkedList is palindrome or not. I hope you know what a Palindrome is. (Check here)

We are going to discuss two approaches to this problem.

Approach 1: Using ArrayList: The basic idea behind this approach is to store all the node values in an ArrayList. After that, we traverse the list for start and end, and keep comparing the values at start index and end index. If they are equal then increase start index and decrease end index. If two values are not the same, then we return **false**(the LinkedList is not a palindrome).

Time Complexity:O(n), for traversing the LinkedList

Space Complexity:O(n), using ArrayList for storing the node values

Approach 2: In this method, we will use LinkedList manipulations.

If the length of the LinkedList is even :

Find the middle point of the LinkedList.

Reverse the second half.

Compare the reverse list to the first half of the list, if all the values are equal return true else return false

If the length of the LinkedList is odd:

Find the middle point of the LinkedList. As the length is odd, the middle point will be between the first half and second half of the LinkedList.

Now reverse the second half of the Linked List

Compare the reverse list to the first half of the list, if all the values are equal return true else return false

The code is given below.

Time Complexity:O(n), for traversing the LinkedList

Space Complexity:O(1), No additional space is used

The code can be found here

# LeetCode

I have been solving Leetcode problems for around a year or so. Suddenly I have developed a passion of writing tutorials for these problems. I am starting with Leetcode problem, in future I will try to make tutorials on Spring,Android,Java,Algorithms and many more.

Follow me on medium - https://sourav-saikia.medium.com

Follow me on dev.to - https://dev.to/sksaikia

Follow me on twitter - https://twitter.com/sourav__saikia

Connect on Linkedin - www.linkedin.com/in/sourav-kumar-saikia

The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.

Problem Name | Problem No | Article Links |
---|---|---|

Contains Duplicate | 217 | https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0 |

Jewels and Stones | 771 | https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37 |

Design Authentication Manager | 1797 | https://sourav-saikia.medium.com/leetcode-1797-design-authentication-manager-biweekly-contest-48-8ef4d82a220d |

## March LeetCoding Challenge

Problem Name | Problem No | Article Links |
---|---|---|

Distribute Candies | 575 | https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9 |

Set Mismatch | 645 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9 |

Missing Number | 268 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb |

Intersection of Two Linked Lists | 160 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563 |

Average of Levels in Binary Tree | 637 | https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8 |

Short Encoding of Words | 820 |

## Discussion (0)