234. Palindrome Linked List
Palindrome Linked List (LeetCode 234) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Linked List Manipulation Patterns pattern, in the In-place Reversal subpattern.
How to solve Palindrome Linked List
Palindrome Linked List is a In-Place Linked List Reversal problem, part of Linked List Manipulation Patterns. Master in-place linked list reversal including full reversal, partial reversal, and k-group reversal techniques.
Work towards the solution in these steps:
- Consider how you might verify a palindrome property by comparing elements from both ends of the list.
- Think about how to find the midpoint of the linked list efficiently, possibly using two pointers moving at different speeds.
- Once you find the midpoint, consider reversing the second half of the list to facilitate comparison without extra space.
The reference solution runs in O(n) time and O(1) space.
The Palindrome Linked List solution and editorial walks through the full approach with reference code.
Problem statement
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
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?
Topics and companies
Topics: Linked List, Two Pointers, Stack, Recursion.
Reported in interviews at Microsoft, Facebook, Amazon, Adobe, Capital One, Google, Oracle, Bloomberg, Uber, Snapchat, PayTM.
How to practise Palindrome Linked List on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open Palindrome Linked List in the code editor, or read the Palindrome Linked List editorial for a worked solution with its approach and complexity analysis.
Where Palindrome Linked List sits in the DSA pattern sheet
- Linked List Manipulation Patterns pattern guide
- In-place Reversal subpattern
- The full DSA patterns sheet
Problems related to Palindrome Linked List
Other problems that use the same In-place Reversal and Linked List Manipulation Patterns techniques:
- Remove Duplicates from Sorted List — Easy, same subpattern
- Remove Duplicates from Sorted List II — Medium, same subpattern
- Reverse Linked List — Easy, same subpattern
- Reverse Linked List II — Medium, same subpattern
- Reverse Nodes in k-Group — Hard, same subpattern
- Add Two Numbers — Medium, same pattern
Palindrome Linked List FAQ
What is the LeetCode number of Palindrome Linked List?
Palindrome Linked List is LeetCode problem 234, rated Easy.
What pattern is used to solve Palindrome Linked List?
Palindrome Linked List is a In-Place Linked List Reversal problem. It belongs to the Linked List Manipulation Patterns pattern, in the In-place Reversal subpattern.
What is the time complexity of Palindrome Linked List?
The reference solution runs in O(n) time and O(1) space.
Which companies ask Palindrome Linked List?
Palindrome Linked List has been reported in interviews at Microsoft, Facebook, Amazon, Adobe, Capital One, Google, Oracle, Bloomberg, Uber, Snapchat, PayTM.