Dare2Solve
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.
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.
Find the Middle of the Linked List:
slow
and fast
. slow
moves one step at a time, while fast
moves two steps at a time. By the time fast
reaches the end of the list, slow
will be at the middle.Reverse the Second Half of the Linked List:
Compare the Two Halves:
Restore the List (Optional):
O(n)
O(n/2)
), reverse the second half (O(n/2)
), and then compare the two halves (O(n/2)
).O(1)
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;
}
};
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
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;
}
}
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;
};