每日一练：回文链表
一、题目要求
给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表
。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1] 输出：true
示例 2：
输入：head = [1,2] 输出：false
提示：
- 链表中节点数目在范围
[1, 105]内 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
以上内容来自LeetCode
二、解法1-反转回文链表 进阶
回文链表是对称的，只要将右边反转，那么两边就变成了一样的，此时进行比较，如果不同就不是回文链表。
class Solution {
public:bool isPalindrome(ListNode* head) {int count = 0;ListNode* cur = head;while (cur) {count++;cur = cur->next;}ListNode* curr = head;int half = count / 2 + count % 2; //链表长度是奇数，最中间的节点不用处理while (half--) {curr = curr->next;}if(curr == nullptr) // 如果链表只有一个节点return true;// 反转链表ListNode* prev = curr;curr = curr->next;prev->next = nullptr;while(curr){ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}cur = head;while(prev){if(prev->val != cur->val)return false;prev = prev->next;cur = cur->next;}return true;}
};
三、解法2-递归 进阶
解法1需要反转链表，这种方式不够优雅，我们可以用递归的方式遍历链表的右半部分，这样不用修改链表。
主要思想是维护一个cur的二级指针，当curr到最后时才进行比较，相同则修改*cur指向下一个节点，然后函数返回，此时curr指向上一个节点，依次继续比较。
class Solution {bool _isPalindrome(ListNode** pcur, ListNode* curr) {if (curr == nullptr)return true;bool ret = _isPalindrome(pcur, curr->next); if(ret == false) // 为假说明不对称return false;if (curr->val == (*pcur)->val) {(*pcur) = (*pcur)->next; // 修改curreturn true;}return false;}public:bool isPalindrome(ListNode* head) {int count = 0;ListNode* cur = head;while (cur) {count++;cur = cur->next;}ListNode* curr = head;int half = count / 2 + count % 2;while (half--) {curr = curr->next;}return _isPalindrome(&head, curr);}
};