DEV Community

loading...
Cover image for April LeetCoding Challenge 2021 — Day 1: Palindrome Linked List

April LeetCoding Challenge 2021 — Day 1: Palindrome Linked List

sksaikia profile image Sourav ・2 min read

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
Enter fullscreen mode Exit fullscreen mode

Example 2:

**Input:** head = [1,2]
**Output:** false
Enter fullscreen mode Exit fullscreen mode

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

Diagram representing LinkedList with even number of nodes

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

Diagram representing LinkedList with odd number of nodes

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.

March LeetCoding Challenge

Discussion (0)

pic
Editor guide