Description
Given a singly linked list, determine if it is a palindrome.
设计一种方式检查一个链表是否为回文链表。
Examples
Input: 1->2
Output: false
Answer
Find the middle point of the input linked list and reverse the second part of the list then compare the value with the first part.
The solution of reverse singly linked list: LeetCode 206. Reverse Linked List
Time Complexity
O(n)
Code
C++
class Solution {
public:
ListNode* findmid(ListNode *node)
{
if(!head || !head->next) return node;
ListNode *slow = node, *fast = node->next;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* reverse(ListNode *node)
{
if(!head || !head->next) return node;
ListNode* pre = nullptr;
while(node)
{
ListNode* tmp = node->next;
node->next = pre;
pre = node;
node = tmp;
}
return pre;
}
bool isPalindrome(ListNode* head){
if(!head || !head->next) return true;
ListNode *mid = findmid(head);
mid->next = reverse(mid);
mid = mid->next;
while(head && mid)
{
if(head->val != mid->val) return false;
head = head->next;
mid = mid->next;
}
return true;
}
};
