Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given the head of a singly linked list, return true if it is a palindrome.
Input/Output Specifications
- Input: Head of a singly linked list
- Output: Boolean indicating if the list is a palindrome
- Constraints:
- The number of nodes in the list is in the range [1, 10^5]
- 0 <= Node.val <= 9
Examples
Example 1:
Input: head = [1,2,2,1]
Output: true
Example 2:
Input: head = [1,2]
Output: false
Solutions
Approach 1: Reverse Second Half (Optimal)
This approach finds the middle of the list, reverses the second half, and then compares both halves.
Algorithm:
- Find the middle of the linked list using slow and fast pointers
- Reverse the second half of the list
- Compare the first half with the reversed second half
- Optionally restore the original list by reversing the second half again
Python:
def isPalindrome(head):
"""
Check if linked list is palindrome by reversing second half
Time: O(n)
Space: O(1)
"""
if not head or not head.next:
return True
# Find the middle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse the second half
second_half = reverseList(slow)
# Compare both halves
first_half = head
while second_half:
if first_half.val != second_half.val:
return False
first_half = first_half.next
second_half = second_half.next
return True
def reverseList(head):
"""Helper function to reverse a linked list"""
prev = None
current = head
while current:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev
Java:
class Solution {
/**
* Check if linked list is palindrome by reversing second half
* Time: O(n)
* Space: O(1)
*/
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
// Find the middle
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse the second half
ListNode secondHalf = reverseList(slow);
// Compare both halves
ListNode firstHalf = head;
while (secondHalf != null) {
if (firstHalf.val != secondHalf.val) {
return false;
}
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
}
Go:
// isPalindrome - Check if linked list is palindrome by reversing second half
// Time: O(n)
// Space: O(1)
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
// Find the middle
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
// Reverse the second half
secondHalf := reverseList(slow)
// Compare both halves
firstHalf := head
for secondHalf != nil {
if firstHalf.Val != secondHalf.Val {
return false
}
firstHalf = firstHalf.Next
secondHalf = secondHalf.Next
}
return true
}
// reverseList - Helper function to reverse a linked list
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
current := head
for current != nil {
nextTemp := current.Next
current.Next = prev
prev = current
current = nextTemp
}
return prev
}
JavaScript:
/**
* Check if linked list is palindrome by reversing second half
* Time: O(n)
* Space: O(1)
*/
function isPalindrome(head) {
if (head === null || head.next === null) {
return true;
}
// Find the middle
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse the second half
const secondHalf = reverseList(slow);
// Compare both halves
let firstHalf = head;
let current = secondHalf;
while (current !== null) {
if (firstHalf.val !== current.val) {
return false;
}
firstHalf = firstHalf.next;
current = current.next;
}
return true;
}
/**
* Helper function to reverse a linked list
*/
function reverseList(head) {
let prev = null;
let current = head;
while (current !== null) {
const nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
C#:
public class Solution {
/// <summary>
/// Check if linked list is palindrome by reversing second half
/// Time: O(n)
/// Space: O(1)
/// </summary>
public bool IsPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
// Find the middle
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Reverse the second half
ListNode secondHalf = ReverseList(slow);
// Compare both halves
ListNode firstHalf = head;
while (secondHalf != null) {
if (firstHalf.val != secondHalf.val) {
return false;
}
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}
private ListNode ReverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
}
Approach 2: Using Array (Extra Space)
This approach converts the linked list to an array and checks if the array is a palindrome.
Algorithm:
- Convert the linked list to an array
- Use two pointers to compare elements from start and end
- Return true if all elements match, false otherwise
Python:
def isPalindromeArray(head):
"""
Check if linked list is palindrome using array
Time: O(n)
Space: O(n)
"""
values = []
current = head
# Convert to array
while current:
values.append(current.val)
current = current.next
# Check palindrome
left, right = 0, len(values) - 1
while left < right:
if values[left] != values[right]:
return False
left += 1
right -= 1
return True
Java:
class Solution {
/**
* Check if linked list is palindrome using array
* Time: O(n)
* Space: O(n)
*/
public boolean isPalindromeArray(ListNode head) {
List<Integer> values = new ArrayList<>();
ListNode current = head;
// Convert to array
while (current != null) {
values.add(current.val);
current = current.next;
}
// Check palindrome
int left = 0, right = values.size() - 1;
while (left < right) {
if (!values.get(left).equals(values.get(right))) {
return false;
}
left++;
right--;
}
return true;
}
}
Go:
// isPalindromeArray - Check if linked list is palindrome using array
// Time: O(n)
// Space: O(n)
func isPalindromeArray(head *ListNode) bool {
var values []int
current := head
// Convert to array
for current != nil {
values = append(values, current.Val)
current = current.Next
}
// Check palindrome
left, right := 0, len(values)-1
for left < right {
if values[left] != values[right] {
return false
}
left++
right--
}
return true
}
JavaScript:
/**
* Check if linked list is palindrome using array
* Time: O(n)
* Space: O(n)
*/
function isPalindromeArray(head) {
const values = [];
let current = head;
// Convert to array
while (current !== null) {
values.push(current.val);
current = current.next;
}
// Check palindrome
let left = 0, right = values.length - 1;
while (left < right) {
if (values[left] !== values[right]) {
return false;
}
left++;
right--;
}
return true;
}
C#:
public class Solution {
/// <summary>
/// Check if linked list is palindrome using array
/// Time: O(n)
/// Space: O(n)
/// </summary>
public bool IsPalindromeArray(ListNode head) {
List<int> values = new List<int>();
ListNode current = head;
// Convert to array
while (current != null) {
values.Add(current.val);
current = current.next;
}
// Check palindrome
int left = 0, right = values.Count - 1;
while (left < right) {
if (values[left] != values[right]) {
return false;
}
left++;
right--;
}
return true;
}
}
Key Insights
- Space optimization: Reversing second half allows O(1) space solution
- Middle finding: Use slow and fast pointers to find the middle efficiently
- List modification: Temporarily modify the list structure for comparison
- Restoration: Optionally restore the original list structure
- Edge cases: Handle single node and empty lists properly
Edge Cases
- Single node list (always palindrome)
- Two node list (check if values are equal)
- Odd length list (ignore middle node)
- Even length list (compare all nodes)
- Empty list (edge case)
Test Cases
# Test case 1: Palindrome with even length
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(2)
head1.next.next.next = ListNode(1)
# Expected: True
# Test case 2: Not a palindrome
head2 = ListNode(1)
head2.next = ListNode(2)
# Expected: False
# Test case 3: Single node
head3 = ListNode(1)
# Expected: True
# Test case 4: Palindrome with odd length
head4 = ListNode(1)
head4.next = ListNode(2)
head4.next.next = ListNode(1)
# Expected: True
Follow-up Questions
- How would you restore the original list structure?
- Can you solve this using recursion?
- How would you handle very large lists?
- What if the list has duplicate values?
Common Mistakes
- Not handling single node lists correctly
- Incorrectly finding the middle of the list
- Not properly reversing the second half
- Forgetting to compare all elements
- Memory issues when not restoring the original list
- Off-by-one errors in comparison logic