https://leetcode-cn.com/problems/palindrome-linked-list/
思路:快慢指针
//链表反转
ListNode* reverList(ListNode *head) {
ListNode* res = nullptr;
while(head) {
ListNode *temp = head->next;
head->next = res;
res = head;
head = temp;
}
return res;
}
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return true;
}
ListNode *slow = head;
ListNode *faster = head->next;
ListNode *slowhead = slow;
while(faster && faster->next) {
slow = slow->next;
faster = faster->next->next;
}
ListNode *last = slow->next;
slow->next = nullptr;
faster = reverList(last);
while(slowhead && faster) {
//cout << slowhead->val << " " << faster->val << endl;
if (slowhead->val != faster->val) {
return false;
}
slowhead = slowhead->next;
faster = faster->next;
}
//cout << slow->val << endl;
return true;
}