🎨Now live: Try our Free AI Image Generation Feature

Description
Given the head of a singly linked list, determine if it is a palindrome. A linked list is a palindrome if the sequence of values read from the head to the end is the same as the sequence read from the end to the head.
Intuition
A linked list can be considered a palindrome if it reads the same forward and backward. To check this, we can split the list into two halves, reverse the second half, and then compare both halves. If they match, the list is a palindrome.
Approach
- Find the Middle of the Linked List:
- Use two pointers,
slow
andfast
.slow
moves one step at a time, whilefast
moves two steps at a time. By the timefast
reaches the end of the list,slow
will be at the middle. - Reverse the Second Half of the Linked List: - Starting from the middle, reverse the second half of the list. This allows us to compare the first half with the reversed second half directly.
- Compare the Two Halves: - Compare the values of the nodes in the first half and the reversed second half. If all the values match, the linked list is a palindrome.
- Restore the List (Optional): - If needed, reverse the second half again to restore the original list structure.
Complexity
Time Complexity:
O(n)
- We traverse the list to find the middle (
O(n/2)
), reverse the second half (O(n/2)
), and then compare the two halves (O(n/2)
).
Space Complexity:
O(1)
- The algorithm only uses a constant amount of extra space for pointers and variables.
Code
C++
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return true;
}
// Step 1: Find the middle of the linked list
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
// Step 2: Reverse the second half of the linked list
ListNode* prev = nullptr;
ListNode* curr = slow;
while (curr != nullptr) {
ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
// Step 3: Compare the first half and the reversed second half
ListNode* firstHalf = head;
ListNode* secondHalf = prev;
while (secondHalf != nullptr) {
if (firstHalf->val != secondHalf->val) {
return false;
}
firstHalf = firstHalf->next;
secondHalf = secondHalf->next;
}
return true;
}
};
Python
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
string1 = string2 = ""
node = head
while node is not None:
string1 += str(node.val)
string2 = str(node.val) + string2
node = node.next
return string1 == string2
Java
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
// Step 1: Find the middle of the linked list
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse the second half of the linked list
ListNode prev = null;
ListNode curr = slow;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
// Step 3: Compare the first half and the reversed second half
ListNode firstHalf = head;
ListNode secondHalf = prev;
while (secondHalf != null) {
if (firstHalf.val != secondHalf.val) {
return false;
}
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}
}
JavaScript
var isPalindrome = function(head) {
let string1 = string2 = "";
let node = head;
while(node != null){
string1 = `${string1}${node.val}`;
string2 = `${node.val}${string2}`;
node = node.next;
}
return string1 === string2;
};