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 |
Top comments (0)