Palindrome Linked List - Solution & Explanation
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?Approach Overview
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.
Approach 1: Reverse Second Half and Compare
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:
- Use two pointers (slow and fast) to find the middle of the linked list.
- Reverse the second half of the linked list.
- Compare the first half and the reversed second half of the list.
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.
Complexity
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.
Approach 2: Convert to Array and Use Two Pointers
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:
- Traverse the linked list and store its elements in an array.
- Use two pointers, one starting at the beginning and the other at the end of the array, to compare values.
- If all corresponding elements are identical, the list is a palindrome.
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.
Complexity
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 3: Fast and Slow Pointers
We can use fast and slow pointers to find the middle of the linked list, then reverse the right half of the list. After that, we traverse both halves simultaneously, checking if the corresponding node values are equal. If any pair of values is unequal, it's not a palindrome linked list; otherwise, it is a palindrome linked list.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
JavaScript
C#
Complexity Comparison
| 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. |
| Fast and Slow Pointers | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Palindrome Linked List - Leetcode 234 - Python • NeetCode • 128,691 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Palindrome Linked List easy or hard?
Palindrome Linked List Python/Java solution
How to solve Palindrome Linked List in O(n)?
What is the best approach for Palindrome Linked List?
Is Palindrome Linked List asked at Google/Amazon/Meta?
What data structure is used in Palindrome Linked List?
What is the time complexity of Palindrome Linked List?
Ready to solve this problem?
Practice Palindrome Linked List with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor