## DEV Community # April LeetCoding Challenge 2021 — Day 1: Palindrome Linked List

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