1. 题目来源

链接：lc234. 回文链表

2. 题目说明

类似题目：

[链表] lc143. 重排链表(反转链表+链表中点+边界问题+经典综合)

3. 题目解析

方法一：逆置+恢复现场

和 [链表] lc143. 重排链表(反转链表+链表中点+边界问题+经典综合) 的思路大致相同

• 对后半段进行翻转
• 判断前半段和后半段是否对称
• 将后半段再翻转回来，恢复现场

感觉这道题目挺综合的，会让你求链表的中间节点，倒数第 k 个节点，以及局部反转链表，再恢复现场。

在做题过程中没有考虑清楚 +-1 的情况，相关地方已经做了注释，供复习、参考~

至于保存数据，额外空间数组来做，没啥意思不再讨论。

参见代码如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {int n = 0;for (auto p = head; p; p = p->next)  ++n;if (n <= 1) return true;int l = n / 2;  // 前半段回文链表节点个数auto a = head;// 走到后半段回文链表的第一个节点即可，n-l指的是找到链表倒数第l个节点// 会将奇数情况下的中间节点归结到左半段，也不需要考虑这个节点for (int i = 0; i < n - l; ++i) a = a->next;// 反转后半段链表，反转完毕，a为链表最后一个节点，b为空// l个节点，反转次数为l-1次，修改了l个节点中的l-1个next指针前后指向关系// 也可以理解为执行一遍翻转for，a就会往后走一个节点，共l个节点，目前处于头结点，共走l-1次，到达尾结点auto b = a->next;for (int i = 0; i < l - 1; ++i) {auto c = b->next;b->next = a;a = b;b = c;}// 双指针进行遍历l次即可        bool flag = true;auto p = head, q = a;for (int i = 0; i < l; ++i) {   if (p->val != q->val) { flag = false; break; }p = p->next;q = q->next;}auto tail = a;  // 得存a的尾结点b = a->next;// 将链表恢复原状，反转后半段for (int i = 0; i < l - 1; ++i) {auto c = b->next;b->next = a;a = b, b = c;}a->next = NULL;return flag;}
};