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:
[1, 105].0 <= Node.val <= 9Follow up: Could you do it in
O(n) time and O(1) space?Problem Overview: You are given the head of a singly linked list. The goal is to determine whether the sequence of node values reads the same forward and backward. In other words, check if the linked list forms a palindrome without modifying the logical order of elements.
Approach 1: Convert to Array and Use Two Pointers (O(n) time, O(n) space)
This approach copies the linked list values into a dynamic array or vector while iterating through the list once. After that, apply the classic two pointers technique: one pointer starts at the beginning of the array and the other at the end. Compare elements while moving inward. If every pair matches, the sequence is a palindrome.
The key insight is that arrays allow constant-time index access, which makes comparing mirrored elements trivial. This solution is straightforward to implement and easy to reason about, especially for beginners. The tradeoff is additional memory because the entire list is stored in an array.
Approach 2: Reverse Second Half and Compare (O(n) time, O(1) space)
This is the optimal in-place technique commonly expected in interviews. First locate the midpoint of the list using the fast and slow pointer technique from two pointers. When the fast pointer reaches the end, the slow pointer sits at the middle. Reverse the second half of the list starting from that midpoint.
Once reversed, compare nodes from the beginning of the list with nodes from the reversed half. If every value matches, the linked list is a palindrome. Reversal works because the second half now appears in reverse order, allowing direct pairwise comparison.
The advantage is constant extra memory since operations happen directly on the linked list. The only additional work is reversing half the list and optionally restoring it afterward. The algorithm performs a single pass to find the midpoint, another pass to reverse, and a final comparison pass, which still results in linear time.
Recommended for interviews: Start by explaining the array approach to demonstrate the core palindrome idea. Then optimize to the in-place method by reversing the second half. Interviewers typically expect the O(n) time and O(1) space solution because it shows comfort with linked list manipulation and pointer techniques.
This approach involves reversing the second half of the linked list and then comparing it with the first half. If they are identical, the linked list is a palindrome. The steps include:
The above solution in C reverses the second half of the linked list starting from the middle. We use a fast and slow pointer to find the middle together with reversing the second half and checking for equality.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) since we are traversing the list multiple times but each in linear time.
Space Complexity: O(1) as we are reversing the linked list in place.
In this approach, convert the linked list into an array and utilize a two-pointer technique to determine if it forms a palindrome. The steps are as follows:
This C solution creates an array as large as the linked list to store values, which are then checked for palindromic order using two index pointers.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) due to single traversation and subsequent O(n/2) check.
Space Complexity: O(n) because we store all node values in an array.
| Approach | Complexity |
|---|---|
| Reverse Second Half and Compare | Time Complexity: O(n) since we are traversing the list multiple times but each in linear time. |
| Convert to Array and Use Two Pointers | Time Complexity: O(n) due to single traversation and subsequent O(n/2) check. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Convert to Array and Two Pointers | O(n) | O(n) | When simplicity matters and extra memory is acceptable |
| Reverse Second Half and Compare | O(n) | O(1) | Best for interviews and memory-constrained scenarios |
L10. Check if a LinkedList is Palindrome or Not | Multiple Approaches • take U forward • 146,459 views views
Watch 9 more video solutions →Practice Palindrome Linked List with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor