234. Palindrome Linked List
1. Description
Given a singly linked list, determine if it is a palindrome.
2. Example
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
3. Follow Up
Could you do it in O(n) time and O(1) space?
4. Solutions
My Accepted Solution(Follow Up)
n is count of numbers in m_head
Time complexity: O(n)
Space complexity: O(1)
// we use slow and fast pointers to find the middle of m_head
// then, we reverse the later half of m_head
// so, we could get the head of the first half and the head of the reversed second half
// then, we could compare them as the definition of a palindrome
class Solution
{
private:
ListNode* reverseList(ListNode *m_head)
{
if(!m_head) return nullptr;
auto lastReversedIter = m_head, firstUnreversedIter = m_head->next;
lastReversedIter->next = nullptr;
while(firstUnreversedIter)
{
auto nextNode = firstUnreversedIter->next;
firstUnreversedIter->next = lastReversedIter;
lastReversedIter = firstUnreversedIter;
firstUnreversedIter = nextNode;
}
return lastReversedIter;
}
public:
// bool isPalindrome(ListNode* head)
bool isPalindrome(ListNode *m_head)
{
if(!m_head || !m_head->next) return true;
ListNode *middleNode;
for(auto slowIter = m_head, fastIter = m_head->next; fastIter; slowIter = slowIter->next, fastIter = (fastIter->next ? fastIter->next->next : nullptr))
middleNode = slowIter;
middleNode = middleNode->next;
auto reversedLaterHalfHead = reverseList(middleNode);
while(m_head && reversedLaterHalfHead)
{
if(m_head->val != reversedLaterHalfHead->val) return false;
m_head = m_head->next;
reversedLaterHalfHead = reversedLaterHalfHead->next;
}
return true;
}
};